59 把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

代码一

思想,这段代码很厉害,根本想不到,根据前序遍历的特性,然后题目又要求一层层的遍历从左到右,
那么前序遍历一开始也是先遍历树的最左边,也就是每一层的第一个节点.然后神奇的时作者通过遍历深度加深一次那么数组就扩容一次很巧妙.
比如二叉树{1,2,3,4,5,6,7};
那么代码应该是这样的一开始是{1},{2},{4}然后变成{1},{2},{4,5}然后{1},{2,3},{4,5}然后{1},{2,3},{4,5,6,7}就这样OK了

//用递归做的
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }
    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
        if(root == null) return;
        if(depth > list.size())
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);
        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }
}

代码二

思想
通过队列实现层次遍历

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();        
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)return list;
        q.add(pRoot);
        while(!q.isEmpty()) {
            ArrayList<Integer> arr = new ArrayList<Integer>();
            int len = q.size();
            for(int i=0;i<len;i++) {
                TreeNode temp = q.poll();
                if(temp==null)continue;
                arr.add(temp.val);    
                q.add(temp.left);
                q.add(temp.right);
            }
            if(!arr.isEmpty()) {
                list.add(arr);
            }            
        }        
        return list;        
    }