[leetcode] Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

思路：层序遍历，用queue来搞，但是这题目输出要一层一层分开，所以可以

　　每层插入null作为分割点
　　或者维护两个变量分别记录当前层节点数和下一层节点数，进queue增加，出queue减，等于0表示这一层结束
　　在每层开始处理前记录每层的节点数量numLevel，即为当前queue的大小

思路2：BFS

记录每层的节点数量numLevel：

class Solution {
    public List<List<Integer>> levelOrder (TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root==null)
            return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            int numLevel = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            for(int i =0;i<numLevel;i++){
                TreeNode out = queue.remove();
                list.add(out.val);
                if(out.left!=null)
                    queue.add(out.left);
                if(out.right!=null)
                    queue.add(out.right);
            }
            result.add(list);
        }
        
        return result;
    }
}

用null分割

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return res;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        queue.add(null);

        List<Integer> tmp = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            if (node == null) {
                res.add(new ArrayList<Integer>(tmp));
                tmp.clear();
                if (!queue.isEmpty())
                    queue.add(null);
            } else {
//                System.out.println(node.val);
                tmp.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);

            }

        }
        return res;

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        System.out.println(new Solution().levelOrder(root));

    }

}

View Code

第二遍记录：注意null分层的运用细节。

思路2 BFS实现，传递level下去，每层往对应level的List里增加。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null){
            return res;
        }
        levelHelper(root, 0, res);
        return res;
    }
    
    private void levelHelper(TreeNode node, int level, List<List<Integer>> res){
        //create item for the first time
        if(res.size()<=level){
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(node.val);
        
        if(node.left!=null){
            levelHelper(node.left, level+1, res);
        }
        if(node.right!=null){
            levelHelper(node.right, level+1, res);
        }
    }
    
}

参考：

http://blog.csdn.net/xiaozhuaixifu/article/details/12218869