描述

题目描述

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

示例

输入：{8,6,10,5,7,9,11}
返回值：[[8],[6,10],[5,7,9,11]]

知识点：二叉树，BFS
难度：⭐⭐⭐

题解

解题思路

既然是最终结果是按层打印，分别收集每一层的结点的值，最容易想到的肯定是按层进行层序遍历，而层序遍历或BFS广度优先遍历，一般通过队列实现，栈也可以。

方法一：层序遍历

图解

算法流程：

• 维护一个队列，每次只保存当前层的结点
• 通过两个左右指针，对每一层的遍历从左指针遍历到右指针，同时收集结果
• 对每个结点，如果有子节点，则按顺序加入左右子节点到队列，为下一层遍历做准备

Java 版本代码如下：

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        if(pRoot == null) {
            return res;
        }
        // 队列每次只保存当前层的结点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while(!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            // lo为每一层的左边结点指针，hi为右边结点指针
            int lo = 0, hi = queue.size();
            // 从左到右按顺序遍历当前层的每一个节点
            while(lo++ < hi) {
                TreeNode node = queue.poll();
                // 收集当前层每一个结点的值
                if(node != null) {
                    list.add(node.val);
                }
                // 按顺序加入左右子节点，为下一层遍历做准备
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 收集当前层的结果集
            res.add(list);
        }
        return res;
    }
}

Python 版本代码如下：

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        # 层次遍历
        result = []
        # 借助队列实现
        que = []
        que.append(pRoot)
        temp = pRoot
        # 遍历每一层
        while len(que)>0:
            sz = len(que)
            ans = []
            # 遍历当前层每个结点
            for i in range(sz):
                node = que[0]
                ans.append(node.val)
                que.pop(0)
                if node.left :
                    que.append(node.left)
                if node.right :
                    que.append(node.right)
            result.append(ans)
        return result

复杂度分析：

时间复杂度 O(MN)：M为树的层数，N为每一层的结点数
空间复杂度 O(N)：借助队列实现