【Py/Java/C++三种语言详解】LeetCode每日一题240215【二叉树BFS】LeetCode107、二叉树的层序遍历II

有LeetCode交流群/华为OD考试扣扣交流群可加：948025485
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

题目链接
题目描述
解题思路
- DFS和BFS异同
- 用队列维护的BFS
代码
- Python
- Java
- C++
- 时空复杂度
相关习题
华为OD算法/大厂面试高频题算法练习冲刺训练

题目链接

LeetCode107、二叉树的层序遍历II

题目描述

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：[[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

解题思路

DFS和BFS异同

二叉树层序遍历是一个非常经典的问题，属于必须掌握的题目。

所谓二叉树遍历（traversal）指的是按照一定次序系统地访问一棵二叉树，使每个节点恰好被访问一次。

二叉树遍历实质上是二叉树的线性化，将树状结构变为线性结构。

二叉树遍历有两大类：

深度优先（depth first traversal，DFS）：先完成一棵子树的遍历再完成另一棵
广度优先（breath first traversal，BFS）：先完成一层节点的遍历再完成下一层

DFS和BFS均为树/图的搜索方式，能够访问树/图中的所有节点。它们的特点可以从以下的比喻看出区别：

DFS：优先移动节点，当对给定节点尝试过每一种可能性之后，才退到前一节点来尝试下一个位置。就像一个搜索者尽可能地深入调查未知的地域，直到遇到死胡同才回头。（下图以前序遍历为例）

在这里插入图片描述

BFS：优先对给定节点的下一个位置进行进行尝试，当对给定节点尝试过每一种可能性之后，才移动到下一个节点。就像一只搜索军队铺展开来覆盖领土，直到覆盖了所有地域。

在这里插入图片描述

用队列维护的BFS

树的广度优先遍历亦可称为层序遍历。其核心特点为，从上到下、从左到右访问树中的节点，每一层的节点都按顺序出现。

在这里插入图片描述

本题就是二叉树BFS的板子题，必须掌握。

BFS通常需要通过维护一个先进先出（First In First Out，FIFO) 的队列来实现。

在这里插入图片描述

我们需要构建一个队列q用于储存每一层的所有节点，然后执行while循环（循环不变量为q不为空）：

获得当前队列长度qSize，为该层的节点个数
初始化一个空的子列表subList，用于储存二叉树该层所有节点的值
执行for循环，循环qSize次。每一次循环包含以下环节
a. 令队列q的队头节点出队，记为node，并将其值node.val存入subList中
b. 若node的左孩子node.left存在，则令node.left从队尾入队
c. 若node的右孩子node.right存在，则令node.right从队尾入队
（这些后入队的节点会在下一层的遍历中被取出）
经过qSize次循环后，subList已经储存了这一层节点的所有值，将subList加入全局的答案变量ans中

这样就就是二叉树BFS的基本过程，其中第3步是最关键的步骤。

如果题目有明显地要求区分每一层的情况（比如本题要求每一层的节点值需要单独储存在一个子列表中），则循环qSize次这个步骤是必要的。

本题沿用了LeetCode102、二叉树的层序遍历的大体框架，但最后要求返回的结果是自底向上的层序遍历，只需要返回ans数组的反转即可。即

return ans[::-1]

代码

Python

from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:    # 若根节点为空，返回一个空列表
            return []
        ans = list()    # 初始化答案列表
        q = deque()     # 维护一个队列，用于BFS过程
        q.append(root)  # 初始化队列，加入根节点
        while(len(q) != 0):     # 循环遍历，进行BFS，退出循环的条件是队列为空
            qSize = len(q)      # 获得当前队列的长度，为二叉树该层节点数
            subList = list()    # 初始化子列表，用于储存二叉树该层节点的值
            for i in range(qSize):          # 循环qSize次，遍历该层的节点
                node = q.popleft()          # 令队头的节点node出队
                subList.append(node.val)    # 将node的值加入子列表中
                if node.left:           # 若node的左节点存在，入队
                    q.append(node.left)
                if node.right:          # 若node的右节点存在，入队
                    q.append(node.right)
            ans.append(subList) # 经过循环qSize次后，将子列表加入答案列表
        return ans[::-1]      # 退出while循环，返回答案列表

Java

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> subList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                subList.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(0, subList);
        }

        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            vector<int> subList;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                subList.push_back(node->val);
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            ans.insert(ans.begin(), subList);
        }

        return ans;
    }
};

时空复杂度

时间复杂度：O(N)。仅需一次遍历整棵树。

空间复杂度：O(M)。M为层的最大节点数，队列所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多