Easy

题目描述

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]

示例 3：

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

示例 4：

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

提示：

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

进阶： 递归算法很简单，你可以通过迭代算法来实现吗？

解题思路

解题思路

后序遍历的顺序是：左子树 → 右子树 → 根节点。本题有三种主要解法：

方法一：递归解法（最直观）

递归是最自然的解法，按照后序遍历的定义递归访问节点即可。先递归遍历左子树，再递归遍历右子树，最后访问当前节点。

方法二：迭代解法（栈模拟）

使用栈来模拟递归过程。关键是要记录节点的访问状态，因为在后序遍历中，当我们第一次访问节点时不能立即处理，需要先处理其子节点。可以使用额外的集合记录已访问的节点，或者使用双栈的技巧。

方法三：逆向思维（推荐）

最巧妙的方法是逆向思维：后序遍历的逆序就是"根→右→左"的遍历。我们可以按照"根→右→左"的顺序遍历（类似前序遍历，但先访问右子树），然后将结果反转即可得到后序遍历结果。这种方法代码简洁且易理解。

下面给出的是逆向思维的迭代解法，它既避免了递归的空间开销，又比传统迭代方法更简洁。

代码实现

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        
        stack<TreeNode*> stk;
        stk.push(root);
        
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            result.push_back(node->val);
            
            if (node->left) stk.push(node->left);
            if (node->right) stk.push(node->right);
        }
        
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        return result[::-1]

public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        var result = new List<int>();
        if (root == null) return result;
        
        var stack = new Stack<TreeNode>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            var node = stack.Pop();
            result.Add(node.val);
            
            if (node.left != null) stack.Push(node.left);
            if (node.right != null) stack.Push(node.right);
        }
        
        result.Reverse();
        return result;
    }
}

var postorderTraversal = function(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要访问每个节点一次，其中 n 是树中节点的数量
空间复杂度O(h)栈的最大深度为树的高度 h，最坏情况下为 O(n)

相关题目