描述

题目描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

示例
输入：{1,2,3,4,#,#,5}
返回值：[[1],[2,3],[4,5]]

知识点：树，层序遍历，队列，栈
难度：⭐⭐

题解

解题思路

层序遍历一般都可以通过队列或栈实现

如果是队列，每次需要加入当前层所有结点到队头，之后收集完当前层所有结点的值后，再加入下一层所有结点，直到叶子结点

方法一：队列实现

图解

image-20210715214359892

算法流程：
  • 维护一个队列，队列保存每一层所有结点
  • list集合收集当前层的所有结点的值
  • 遍历所有每一层，从队列中取出当前层所有结点，并收集结果到集合
  • 左右节点按顺序加到队尾
Java 版本代码如下：
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();        
        if(root == null) {
            return res;
        }        
        // 队列保存每一层所有结点
        Queue<TreeNode> queue = new LinkedList<>();
        // 先放入根节点
        queue.offer(root);
        while(!queue.isEmpty()) {
            // 收集当前层的所有结点的值
            ArrayList<Integer> list = new ArrayList<>();
            // ·当前层的节点数量
            int count = queue.size();
            // 遍历每一层
            while(count-- > 0) {
                // 从对头取出节点
                TreeNode node = queue.poll();
                // 收集结果
                list.add(node.val);
                // 左右节点按顺序加到队尾
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}
Python 版本代码如下：
class Solution:
    def levelOrder(self , root ):
        # write code here
        #队列解决
        qune, res = [], []
        if not root:
            return res
        # 队列保存每一层所有结点
        qune.append(root)
        while len(qune)!=0:
            n = len(qune)
            temp = []
            # 遍历每一层
            for i in range(n):
                node = qune.pop(0)
                temp.append(node.val)
                # 左右节点按顺序加到队尾
                if node.left:
                    qune.append(node.left)
                if node.right:
                    qune.append(node.right)
            res.append(temp)
        return res
复杂度分析：

时间复杂度 O(N)：
空间复杂度 O(N)：用到了队列和集合

方法二：递归

算法流程：
  • 定义递归函数功能：遍历当前层depth的所有结点并收集结果到list
  • depth用来表示层数，作为list的索引
  • 每次递归时，初始化集合，该集合用来保存层数为depth时的结点值，depth相当于结果集合list的索引
  • 递归直到叶子节点后，收集层数为depth的结果集，接着继续递归右子结点
Java 版本代码如下：
import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        DFS(root,res,0);
        return res;
    }
    // 递归函数功能：遍历当前层depth的所有结点并收集结果到list
    // depth用来表示层数，作为list的索引
    public void DFS(TreeNode root, ArrayList<ArrayList<Integer>> list, int depth){
        // 递归终止条件
        if(root == null) {
            return;
        }
        // 初始化集合，该集合用来保存层数为depth时的结点值，depth相当于结果集合list的索引
        if(list.size() == depth) {
            list.add(new ArrayList<>());
        }
        // dfs，递归直到叶子节点
        DFS(root.left, list, depth + 1);
        // 收集层数为depth的结果集
        list.get(depth).add(root.val);
        DFS(root.right, list, depth + 1);
    }
}
复杂度分析：

时间复杂度 O(N)：递归所需要的时间
空间复杂度 O(N)：递归所需要的栈空间，N为节点数