03、二叉树的层序遍历II

今天我们来看一个经典题目 https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

题目描述

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

示例 1：

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

        3
       / \
      9  20
        /  \
       15   7

示例 2：

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

示例 3：

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

数据范围：

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

题目分析

这道题是经典的层序遍历问题，但要求结果是自底向上的。所以和我们的层序遍历是有区别的，不过我们看到这个题目，应该也可以想到，先层序遍历，再翻转的解题思路

层序遍历：按照从上到下、从左到右的顺序遍历二叉树的每一层

自底向上：将遍历结果反转，或者使用特殊的存储方式

既然如此，那这个题目我们要注意以下关键点

• 需要明确区分每一层的节点
• 需要按层记录节点值
• 最后需要将结果反转

BFS（广度优先搜索）+ 反转

算法思路

1. 使用队列实现层序遍历
2. 遍历每一层时，记录当前层的所有节点值
3. 将每层结果添加到结果列表中
4. 最后将结果列表反转

图解过程

以 root = [3,9,20,null,null,15,7] 为例：

初始状态：
        3
       / \
      9  20
        /  \
       15   7

第一层遍历：
队列：[3]
当前层：[3]
结果：[[3]]

第二层遍历：
队列：[9, 20]
当前层：[9, 20]
结果：[[3], [9, 20]]

第三层遍历：
队列：[15, 7]
当前层：[15, 7]
结果：[[3], [9, 20], [15, 7]]

反转结果：
[[15, 7], [9, 20], [3]]

cpp

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;

        // 特殊情况：空树
        if (root == nullptr) {
            return result;
        }

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

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;

            // 遍历当前层
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);

                // 将子节点加入队列
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            result.push_back(currentLevel);
        }

        // 反转结果
        reverse(result.begin(), result.end());
        return result;
    }
};

DFS（深度优先搜索）

其实这个题目最好的解决方式就是层级遍历，只学上一种解题方式就好

算法思路

使用递归的 DFS，记录当前节点的层级，将节点值添加到对应层级的列表中。

关键点

1. 使用一个变量 level 记录当前层级
2. 先递归访问子节点（确保结果列表足够长）
3. 将节点值插入到对应层级

#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    // 构造函数（LeetCode 环境中默认存在）
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        // 调用辅助 DFS 函数，初始层级为 0
        dfs(root, 0, result);
        return result;
    }

private:
    // 辅助 DFS 函数：node-当前节点，level-当前层级，result-结果容器（引用传递）
    void dfs(TreeNode* node, int level, vector<vector<int>>& result) {
        // 终止条件：节点为空
        if (node == nullptr) {
            return;
        }

        // 如果当前层级超出结果容器长度，在头部插入空列表（对应底层层级）
        if (level >= result.size()) {
            result.insert(result.begin(), vector<int>());
        }

        // 将当前节点值加入对应层级的列表（从尾部反向定位层级）
        result[result.size() - level - 1].push_back(node->val);

        // 递归遍历左右子树，层级+1
        dfs(node->left, level + 1, result);
        dfs(node->right, level + 1, result);
    }
};