107. 二叉树的层序遍历 II
题目描述
输入二叉树的根节点 root。按层收集节点值，但层的输出顺序要反过来：最深的一层排在最前面，根所在的那一层排在最后。
每一层内部仍然按从左往右的次序排列。
返回这些层组成的列表。空树返回 []。树用层序数组表示，null 代表空位。
示例 1
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
解释：最底层 [15,7] 先输出，根 [3] 最后输出。
示例 2
输入：root = [1] 输出：[[1]]
解释：只有一层。
示例 3
输入：root = [] 输出：[]
解释：空树返回空列表。
数据范围
- 节点总数在
[0, 2000]之间。 -1000 <= Node.val <= 1000
解题思路：广度优先搜索 + 反转
先做普通的自顶向下 BFS：每层记下队列长度，弹出这么多个节点组成一层。所有层都收集完后，把层列表整体反转一次即可。只反转层的顺序，不动层内顺序。
为什么正确
每次进入 while 循环时，队列里恰好是下一层的全部节点，按从左到右排列；res 中已有层按自顶向下排列。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
只反转层的顺序，不要反转每层内部的顺序。题目要求层与层之间自底向上，层内仍从左到右。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
q = collections.deque([root] if root else [])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res[::-1]class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>();
if (root != null) q.offer(root);
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int k = q.size(); k > 0; k--) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
res.add(level);
}
Collections.reverse(res);
return res;
}
}class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
deque<TreeNode*> q;
if (root) q.push_back(root);
while (!q.empty()) {
vector<int> level;
for (int k = q.size(); k > 0; k--) {
TreeNode* node = q.front();
q.pop_front();
level.push_back(node->val);
if (node->left) {
q.push_back(node->left);
}
if (node->right) {
q.push_back(node->right);
}
}
res.push_back(level);
}
reverse(res.begin(), res.end());
return res;
}
};func levelOrderBottom(root *TreeNode) [][]int {
res := [][]int{}
q := []*TreeNode{}
if root != nil {
q = append(q, root)
}
for len(q) > 0 {
level := []int{}
for k := len(q); k > 0; k-- {
node := q[0]
q = q[1:]
level = append(level, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
res = append(res, level)
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}var levelOrderBottom = function(root) {
const res = [];
const q = root ? [root] : [];
while (q.length) {
const level = [];
for (let k = q.length; k > 0; k--) {
const node = q.shift();
level.push(node.val);
if (node.left) {
q.push(node.left);
}
if (node.right) {
q.push(node.right);
}
}
res.push(level);
}
return res.reverse();
};function levelOrderBottom(root: TreeNode | null): number[][] {
const res: number[][] = [];
const q: TreeNode[] = root ? [root] : [];
while (q.length) {
const level: number[] = [];
for (let k = q.length; k > 0; k--) {
const node = q.shift()!;
level.push(node.val);
if (node.left) {
q.push(node.left);
}
if (node.right) {
q.push(node.right);
}
}
res.push(level);
}
return res.reverse();
}其他解法
两种方法都先得到自顶向下的层序结果再整体反转；区别只在按层收集节点用队列还是用递归。
解法 2：深度优先搜索 时间 O(n)，空间 O(h)
递归时带上深度 depth，第一次到达某个深度时新建一层。按先左后右的顺序递归，把节点值追加到第 depth 层。最后把整个层列表反转。
辅助空间取决于树高 h，不需要队列。深链树递归很深，Python 需要调高递归深度。
import sys
class Solution:
def levelOrderBottom(self, root):
sys.setrecursionlimit(10000)
result = []
def dfs(node, depth):
if not node:
return
if depth == len(result):
result.append([])
result[depth].append(node.val)
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
dfs(root, 0)
result.reverse()
return resultclass Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
dfs(root, 0, result);
Collections.reverse(result);
return result;
}
private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
if (node == null) return;
if (depth == result.size()) result.add(new ArrayList<>());
result.get(depth).add(node.val);
dfs(node.left, depth + 1, result);
dfs(node.right, depth + 1, result);
}
}class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
dfs(root, 0, result);
reverse(result.begin(), result.end());
return result;
}
void dfs(TreeNode* node, int depth, vector<vector<int>>& result) {
if (!node) return;
if (depth == (int)result.size()) result.push_back({});
result[depth].push_back(node->val);
dfs(node->left, depth + 1, result);
dfs(node->right, depth + 1, result);
}
};func levelOrderBottom(root *TreeNode) [][]int {
result := [][]int{}
var dfs func(node *TreeNode, depth int)
dfs = func(node *TreeNode, depth int) {
if node == nil {
return
}
if depth == len(result) {
result = append(result, []int{})
}
result[depth] = append(result[depth], node.Val)
dfs(node.Left, depth+1)
dfs(node.Right, depth+1)
}
dfs(root, 0)
for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
result[i], result[j] = result[j], result[i]
}
return result
}var levelOrderBottom = function(root) {
const result = [];
const dfs = (node, depth) => {
if (!node) return;
if (depth === result.length) result.push([]);
result[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return result.reverse();
};function levelOrderBottom(root: TreeNode | null): number[][] {
const result: number[][] = [];
const dfs = (node: TreeNode | null, depth: number): void => {
if (!node) return;
if (depth === result.length) result.push([]);
result[depth].push(node.val);
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
};
dfs(root, 0);
return result.reverse();
};