LeetCode 145. 二叉树的后序遍历

◎

本节目标

用根、右、左的显式栈收集顺序整体反转，得到左、右、根。

这道题属于遍历与层序视角的“离开节点后处理”位置。为避免在迭代中额外记录节点是否第二次到达，主解法把一个容易生成的逆序整体反转。

查看 LeetCode 原题

朴素思路与瓶颈

直接模拟后序常要区分“第一次到达”和“右子树已完成”的状态。这样的标记可行，但会让最基本的遍历逻辑变复杂。

核心不变量

弹出节点时先记录根，并先压左孩子、再压右孩子，实际收集顺序就是根—右—左。将整个结果反转后，三个部分的相对顺序同时翻转，正好成为左—右—根。

正确性依据

栈的后进先出性质保证右子树在左子树之前被处理，因此收集到的是每个子树的根—右—左序列。反转后，子树内部及左右子树的顺序都变为左—右—根，故结果为后序遍历。

代码实现

C++

C++17

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> answer;
        if (root == nullptr) {
            return answer;
        }

        std::stack<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            TreeNode* node = nodes.top();
            nodes.pop();
            answer.push_back(node->val);
            if (node->left != nullptr) {
                nodes.push(node->left);
            }
            if (node->right != nullptr) {
                nodes.push(node->right);
            }
        }
        std::reverse(answer.begin(), answer.end());
        return answer;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        answer: list[int] = []
        nodes = [root]
        while nodes:
            node = nodes.pop()
            answer.append(node.val)
            if node.left is not None:
                nodes.append(node.left)
            if node.right is not None:
                nodes.append(node.right)
        answer.reverse()
        return answer

复杂度分析

节点只入栈、出栈一次，反转线性序列也只需一次扫描，总时间复杂度为 O(n)。栈与结果序列合计使用 O(n) 空间。

易错点

• 压栈顺序写成先右后左，会收集根—左—右，反转后仍不正确。
• 忘记最终反转，直接返回逆后序。
• 空树时仍把空节点压栈并解引用。

模式迁移

当题目要求子树全部处理完才能汇总节点信息时，可先判断是否能把一个易生成的逆序转换为目标后序，减少访问状态。