BinaryTreeLevelOrderTraversal [source code]

public class BinaryTreeLevelOrderTraversal {
static
/******************************************************************************/
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> level = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
            res.add(new ArrayList<Integer>(level));
            level.clear();
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BinaryTreeLevelOrderTraversal.Solution tester = new BinaryTreeLevelOrderTraversal.Solution();
    }
}

常规操作了, 没什么好说的.

一个小的 pitfall

res.add(level);

刚开始add level的时候用的是这个, 这个是不对的, 其他的某一个题目的时候碰到过一次了, 最后这样 add 的其实每一个 level 都指向的是同一个 list. 必须重新 new 一个 list(的指针)出来;

最后的速度是2ms (40%), 题目也比较老了, 可以接受;

discussion里面看到一个用 recursion(DFS) 来做的:

public class Solution {  
    List<List<Integer>> returnList = new ArrayList<List<Integer>>();  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        func(root,0);  
        return returnList;  

    }  
    public void func(TreeNode root,int level)  
    {  
        if(root==null)  
        {  
            return;  
        }  
        //VISIT  
        if(returnList.size() >= level+1)  
        {  
            List<Integer> l = returnList.get(level);  
            l.add(root.val);  
        }  
        else  
        {  

            List<Integer> temp  = new ArrayList<Integer>();  
            temp.add(root.val);  
            returnList.add(level,temp);  
        }  

        //go left and right  
        func(root.left,level+1);  
        func(root.right,level+1);  
    }  
}

这个做法是对的, 而且依赖于一个二维 list 的使用; 当然这个题目, 这个二维 list 的提示比较明显. 如果其他的题目, 比如最后的output 要求你是一个一维的 list, 让你用 DFS 做level order, 也要想到自己建立一个辅助的二维 list;

他的逻辑比较清晰, 就是用 DFS 的思路 iterate, 然后是一个 PreOrder, 每次到一个 node 的时候判断这个 node 是不是它所在的 level 的起点(左边端点);这题好像必须要用 PreOrder 来做? 必须让最左端的大梁上的起点们先把所有的level list都初始化好, 这样后面的才可以顺利的对自己对应的level 的 list 进行修改; 想了一下, PostOrder 和 InOrder 好像也可以, 不过这两种 order 最后得到的二维 list 的第一维的顺序正好就是 reverse 的. 这个也验证了之前总结DFS traversal的时候的一个观念, InOrder 和 PostOrder 其实是一类的, 而 PreOrder 的代码看起来最简单, 其实是单独的自成一类;

public List<List<Integer>> levelOrder(TreeNode root) {  
    List<List<Integer>> res = new ArrayList<List<Integer>>();  
    levelHelper(res, root, 0);  
    return res;  
}  

public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {  
    if (root == null) return;  
    if (height >= res.size()) {  
        res.add(new LinkedList<Integer>());  
    }  
    res.get(height).add(root.val);  
    levelHelper(res, root.left, height+1);  
    levelHelper(res, root.right, height+1);  
}

这个是一个类似的代码;

Problem Description

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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Difficulty:Medium
Total Accepted:174.2K
Total Submissions:444.5K
Contributor: LeetCode
Companies
linkedin facebook amazon microsoft apple bloomberg
Related Topics
tree breadth-first search
Similar Questions
Binary Tree Zigzag Level Order Traversal Binary Tree Level Order Traversal II Minimum Depth of Binary Tree Binary Tree Vertical Order Traversal Average of Levels in Binary Tree