11 binary-tree-level-order-traver

题目描述

给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
3↵ / ↵ 9 20↵ / ↵ 15 7
该二叉树由底层到顶层层序遍历的结果是
[↵ [15,7]↵ [9,20],↵ [3],↵]
如果你不清楚“{1,#,2,3}”的含义的话，请继续阅读
OJ用这样的方法将二叉树序列化：
二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。
例如：
1↵ / ↵ 2 3↵ /↵ 4↵ ↵ 5
上述的二叉树序列化的结果是：”{1,2,3,#,#,4,#,#,5}”.

代码一

public ArrayList<ArrayList<Integer>> levelOrderBottom (TreeNode root) {
        // write code here
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if(root==null)
            return list;
        q.offer(root);
        while(!q.isEmpty()) {
            int len = q.size();
            while(len>0) {
                TreeNode node = q.poll();
                arr.add(node.val);
                if(node.left!=null)
                    q.offer(node.left);
                if(node.right!=null)
                    q.offer(node.right);
                len--;
            }
            if(len==0) {
                list.add(0,arr);
                arr = new ArrayList<Integer>();
            }
        }
        return list;
    }