Leetcode-102-二叉树的层序遍历

Leecode-102-Binary Tree Level Order Traversal

思路：BFS/DFS

题目描述

给定一颗二叉树，按照层序遍历返回节点的值。

  3
 / \
9  20
  /  \
 15   7

返回结果：

[
  [3],
  [9,20],
  [15,7]
]

注意：这里有个坑，返回的是二维数组（并且每个子数组代表在同一层的节点）

Solution：BFS

• BFS使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前的遍历点。

• BFS有以下两个模板

1. 如果不需要确定当前遍历到了哪一层，模板如下：

while queue 不空:
	cur = queue.pop()
	for 节点 in cur的所有相邻节点:
        if 当前节点未访问过:
            queue.push（该节点）

2. 如果要确定当前遍历到了哪一层，BFS模板如下

# 这里的level表示当前遍历到二叉树的哪一层了。（也可以理解在一个图中，已经走了多少步）
# size表示当前遍历层有多少个元素，也就是队列中的元素
# 这里一次性把size元素遍历完，即把当前层的所有元素都向外走了一步
level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

上面两个是通用模板，在任何题目中都可以用，是要记住的！

本题要求二叉树的层次遍历，所以同一层的节点应该放在一起，故使用模板二。

Java

Solution : BFS

• 使用队列保存每层的节点
• 每次把队列里的原先所有节点进行出队列操作
• 再把每个元素的非空左右子节点进入队列。

class Solution{
    public List<List<Integer>> levelOrder(TreeNode root){
        // res 记录最后结果
        List<List<Integer>> result = new LinkedList<>();

        // 特判
        if (root == null){
            return result;
        }

        // 队列（LinkedList实现）
        Queue<TreeNode> queue = new LinkedList<>();

        // 根节点放入队列
        queue.add(root);


        while(!queue.isEmpty()){
            int curSize = queue.size();
            List<Integer> subList = new LinkedList<>();
            for (int i = 0; i < curSize; i++) {
                // 取出队列首元素并删除
                TreeNode curr = queue.poll();
                if (curr != null){
                    // 队首元素放到结果中
                    subList.add(curr.val);
                    // 对子节点进行处理
                    if (curr.left != null){
                        queue.add(curr.left);
                    }
                    if (curr.right != null){
                        queue.add(curr.right);
                    }
                }
            }
            result.add(subList);
        }
        return result;
    }
}

• 时间复杂度：O(n) 每个节点进出队列一次
• 空间复杂度：O(n) 队列的元素不超过n个

Solution : DFS

• 本题使用 DFS 同样能做。
• 题目要求每一层的节点都是从左到右遍历，因此递归时也要先递归左子树、再递归右子树。
• DFS 做本题的主要问题是： DFS 不是按照层次遍历的。
  • 为了让递归的过程中同一层的节点放到同一个列表中,在递归时要记录每个节点的深度 level
  • 递归到新节点要把该节点放入 level 对应列表的末尾。
  • 当遍历到一个新的深度 level，而最终结果 res 中还没有创建 level 对应的列表时,应该在 res 中新建一个列表用来保存该 level 的所有节点。

class Solution{
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        if (root != null){
            dfs(res,root,0);
        }
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode curr, int level) {
        if (res.size() - 1 < level){
            res.add(new ArrayList<Integer>());
        }

        res.get(level).add(curr.val);

        if (curr.left != null){
            dfs(res,curr.left,level + 1);
        }

        if (curr.right != null){
            dfs(res,curr.right,level + 1);
        }
    }
}

Python

Solution :

打赏