LeetCode 145 二叉树后序遍历：递归和迭代巧妙实现

题目描述

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1图片

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

示例 2：

示例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

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

解题思路

方法一：递归

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。递归实现很自然。

关键点：

递归终止条件是空节点
按照后序遍历的顺序访问
用列表存结果

具体步骤：

当前节点为空就返回
递归遍历左子树
递归遍历右子树
把当前节点值加入结果列表

时间复杂度：O(n)，n 是节点数。空间复杂度：O(h)，h 是树高，递归栈的开销。

方法二：迭代（巧用栈）

后序遍历的迭代实现有个技巧：把前序遍历（根->左->右）改成（根->右->左），然后反转结果。

关键点：

用栈存储待访问的节点
先左后右入栈（和前序相反）
最后反转结果数组

具体步骤：

创建栈，根节点入栈
栈不为空时循环：
- 弹出栈顶节点并访问
- 左子节点入栈（如果存在）
- 右子节点入栈（如果存在）
反转结果数组

时间复杂度：O(n) 空间复杂度：O(h)

方法三：Morris遍历的变种

可以修改Morris遍历来实现后序遍历，思路是反转部分路径上的节点值。这个方法比较复杂，实际中用得不多。

关键点：

利用树的空闲指针
不用额外栈空间
需要反转部分路径上的节点值

时间复杂度：O(n) 空间复杂度：O(1)

图解思路

递归遍历分析

以示例1为例：root = [1,null,2,3]

遍历过程：

递归左子树（空）
递归右子树
- 递归节点2的左子树（节点3）
- 递归节点2的右子树（空）
- 访问节点2
访问根节点1

最终输出：[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

最终输出：[4,6,7,5,2,9,8,3,1]

迭代遍历分析

以示例1为例：

步骤	栈的内容	输出数组	说明
初始状态	[1]	[]	将根节点1入栈
第1步	[2]	[1]	弹出并访问1，将2入栈
第2步	[3]	[1,2]	弹出并访问2，将3入栈
第3步	[]	[1,2,3]	弹出并访问3
最后	[]	[3,2,1]	反转结果数组

代码实现

C# 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    // 递归方法
    public IList<int> PostorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        PostorderHelper(root, result);
        return result;
    }
    
    private void PostorderHelper(TreeNode node, List<int> result) {
        if (node == null) {
            return;
        }
        
        PostorderHelper(node.left, result);
        PostorderHelper(node.right, result);
        result.Add(node.val);
    }
    
    // 迭代方法
    public IList<int> PostorderTraversalIterative(TreeNode root) {
        List<int> result = new List<int>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            result.Insert(0, node.val); // 在开头插入
            
            if (node.left != null) {
                stack.Push(node.left);
            }
            if (node.right != null) {
                stack.Push(node.right);
            }
        }
        
        return result;
    }
}

Python 实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 递归方法
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def postorder(node: TreeNode, result: List[int]):
            if not node:
                return
            postorder(node.left, result)
            postorder(node.right, result)
            result.append(node.val)
        
        result = []
        postorder(root, result)
        return result
    
    # 迭代方法
    def postorderTraversalIterative(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.insert(0, node.val)  # 在开头插入
            
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        return result

C++ 实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     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<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postorderHelper(root, result);
        return result;
    }
    
private:
    void postorderHelper(TreeNode* node, vector<int>& result) {
        if (!node) {
            return;
        }
        
        postorderHelper(node->left, result);
        postorderHelper(node->right, result);
        result.push_back(node->val);
    }
    
public:
    // 迭代方法
    vector<int> postorderTraversalIterative(TreeNode* root) {
        vector<int> result;
        if (!root) {
            return result;
        }
        
        stack<TreeNode*> st;
        st.push(root);
        
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.insert(result.begin(), node->val);  // 在开头插入
            
            if (node->left) {
                st.push(node->left);
            }
            if (node->right) {
                st.push(node->right);
            }
        }
        
        return result;
    }
};

性能分析

各语言的性能对比：

实现语言	执行用时	内存消耗
C++	0 ms	8.4 MB
Python	36 ms	15.8 MB
C#	88 ms	39.9 MB

C++性能最好。迭代方法代码中，在结果列表开头插入元素可以避免最后的反转操作，这是个小技巧。

补充说明

代码亮点

提供了递归和迭代两种方式
迭代方法巧妙利用了前序遍历的变种
处理了空树的边界情况

常见错误

忘记处理空树
迭代时入栈顺序错了
没有正确维护后序遍历的顺序（左->右->根）

讨论

有几个问题可以思考一下：

后序遍历的迭代实现为什么比前序和中序都要复杂？
在结果列表开头插入元素和最后反转数组，哪个效率更高？
后序遍历在实际开发中有什么应用场景？（提示：想想删除树节点的情况）

欢迎在评论区讨论。

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。

题目描述

难度

题目链接

示例

示例 1：

示例 2：

示例 3：

示例 4：

提示

解题思路

方法一：递归

方法二：迭代（巧用栈）

方法三：Morris遍历的变种

图解思路

递归遍历分析

迭代遍历分析

代码实现

C# 实现

Python 实现

C++ 实现

性能分析

补充说明

代码亮点

常见错误

相关题目

讨论