二叉树的层序遍历 II

难度：🟡 中等
标签：树、广度优先搜索、二叉树

题目描述#

Note

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

示例 1#

graph TD 3((3)) --- 9((9)) 3((3)) --- 20((20)) 20((20)) --- 15((15)) 20((20)) --- 7((7)) style 15 fill:#d1e8ff,stroke:#333,stroke-width:2px style 7 fill:#d1e8ff,stroke:#333,stroke-width:2px

输出：[[15, 7], [9, 20], [3]]

方案：BFS + 结果反转#

核心思路：这道题其实非常简单，只需要把 102. 二叉树的层序遍历的结果反过来输出就行。

源码实现#

1
#include <algorithm> // 为了使用 reverse
2
#include <queue>
3
#include <vector>
4

5
class Solution {
6
public:
7
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
8
        vector<vector<int>> ans;
9
        if (!root) return ans;
10

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

14
        while (!q.empty()) {
15
            int sz = q.size();
16
            vector<int> curLevel;
17

18
            // 标准层序遍历逻辑
19
            for (int i = 0; i < sz; ++i) {
20
                TreeNode* node = q.front();
21
                q.pop();
22
                curLevel.push_back(node->val);
23

24
                if (node->left) q.push(node->left);
25
                if (node->right) q.push(node->right);
26
            }
27
            ans.push_back(move(curLevel));
28
        }
29

30
        // 调用标准库函数 reverse，将自顶向下的结果反转为自底向上
31
        reverse(ans.begin(), ans.end());
32

33
        return ans;
34
    }
35
};

复杂度分析#

时间复杂度： $O(n)$ 。层序遍历耗时 $O(n)$ ，最后的 reverse 耗时 $O(h)$ ，总复杂度仍为线性。
空间复杂度： $O(n)$ 。主要是队列和结果容器的开销。

总结#

举一反三：很多算法题都是在经典题目上的“微调”。掌握了 102 题的 BFS 模板，本题只是多了一行 reverse。
工具库的使用：在面试中，熟练调用 std::reverse 等标准库函数体现了你对 C++ 工具链的熟悉程度。

Tip

如果题目要求“自底向上”，最稳妥且最高效的办法往往是先“正常做”，最后再一键反转！

音乐

音乐