题目主要信息

1、将一棵n个节点的二叉树按照从上到下按层的方式打印，每层按照从左到右的顺序输出。

方法一：使用队列

具体方法

特例处理： 当树的根节点为空，则直接返回空列表 [] ；

初始化： 打印结果空列表 res ，包含根节点的双端队列 deque ；

BFS 循环： 当 deque 为空时跳出；

新建列表 tmp ，用于临时存储当前层打印结果；

当前层打印循环： 循环次数为当前层节点数（即 deque 长度）；

出队： 队首元素出队，记为 node；

打印： 若为奇数层，将 node.val 添加至 tmp 尾部；否则，添加至 tmp 头部；

添加子节点： 若 node 的左（右）子节点不为空，则加入 deque ；

将当前层结果 tmp 添加入 res ；

返回值： 返回打印结果列表 res 即可；

Java代码

import java.util.*;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        //层次遍历求解，使用队列保存即可！
        Deque<TreeNode> deque = new LinkedList<>();
        if(pRoot==null) return result;
        deque.offer(pRoot);//根节点入队
        while(!deque.isEmpty()){
            ArrayList<Integer> result1 = new ArrayList<>();//保存临时的结果
            int length= deque.size();//看看队中有几个节点
            while(length>0){
                TreeNode now = deque.poll();//删除队头
                result1.add(now.val);
                if(now.left!=null) deque.offer(now.left);
                if(now.right!=null) deque.offer(now.right);
                length--;
            }
            result.add(result1);
        }
        return result;
    }
}

复杂度分析

• 时间复杂度 ：$O(n)O(n)$ n 为二叉树的节点数量
• 空间复杂度 ：$O(n)O(n)$ 最差情况下，即当树为满二叉树时，最多有 n/2 个树节点 同时 在 queue 中，使用$O(n)O(n)$大小的额外空间。

方法二：递归

具体方法

树类的题目除里非递归外，还可以使用递归。只是需要在函数加入记录深度的遍历，每往下一层深度加1，同时保存结果的result正好对应每层一个数组，因此result的大小正好是遍历的深度，由此可以实现递归。

Java代码

import java.util.*;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        help( pRoot,0);
        return result;

    }
     public void help(TreeNode root, int depth){
        if(root != null){
            if(result.size() <= depth) result.add(new ArrayList<>());
            result.get(depth).add(root.val);
            help(root.left, depth+1);
            help(root.right, depth+1);
        }
    }

}

复杂度分析

• 时间复杂度：$O(n)O(n)$，每个结点访问一次
• 空间复杂度：$O(n)O(n)$，递归栈的最大深度