Medium

题目描述

给你二叉树的根节点 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

解题思路

这道题是经典的二叉树层序遍历问题的变种，要求返回自底向上的层序遍历结果。

解法一：BFS + 反转结果（推荐） 使用广度优先搜索（BFS）进行层序遍历，最后将结果反转即可。具体步骤：

  1. 使用队列进行层序遍历
  2. 对每一层，记录当前层的节点数量
  3. 遍历当前层的所有节点，将值加入当前层结果，并将子节点加入队列
  4. 将当前层结果加入总结果
  5. 最后反转整个结果数组

解法二：BFS + 栈/双端队列 在遍历过程中直接将每层结果插入到结果数组的开头，避免最后的反转操作。

解法三：DFS递归 使用深度优先搜索，记录每个节点的深度，将节点值插入到对应深度的数组开头。

第一种解法最直观易懂，代码简洁，是面试中的首选方案。

代码实现

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) 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;
    }
};

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(current_level)
        
        return result[::-1]

public class Solution {
    public IList<IList<int>> LevelOrderBottom(TreeNode root) {
        var result = new List<IList<int>>();
        if (root == null) return result;
        
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        
        while (queue.Count > 0) {
            int levelSize = queue.Count;
            var currentLevel = new List<int>();
            
            for (int i = 0; i < levelSize; i++) {
                var node = queue.Dequeue();
                currentLevel.Add(node.val);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            result.Add(currentLevel);
        }
        
        var reversed = new List<IList<int>>();
        for (int i = result.Count - 1; i >= 0; i--) {
            reversed.Add(result[i]);
        }
        return reversed;
    }
}

var levelOrderBottom = function(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        result.push(currentLevel);
    }
    
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型BFS解法
时间复杂度O(n)
空间复杂度O(w)

其中 n 是二叉树中的节点总数，w 是二叉树的最大宽度。时间复杂度为 O(n) 是因为需要访问每个节点一次。空间复杂度为 O(w) 主要由队列占用的空间决定，最坏情况下队列中会存储二叉树最宽层的所有节点。

相关题目