1、解题思路

后序遍历是二叉树的一种深度优先遍历方式，顺序为：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。可以通过递归或迭代（使用栈）的方式实现后序遍历。

2、代码实现

C++（递归）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        postorder(root, result);
        return result;
    }

  private:
    void postorder(TreeNode* root, vector<int>& result) {
        if (root == nullptr) {
            return ;
        }

        postorder(root->left, result);  // 遍历左子树
        postorder(root->right, result); // 遍历右子树
        result.push_back(root->val);    // 访问根节点
    }
};
C++（迭代）
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <stack>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int> result;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* lastVisited = nullptr;    // 记录上一次访问的节点

        while (cur != nullptr || !s.empty()) {
            while (cur != nullptr) {
                s.push(cur);
                cur = cur->left;    // 左子树入栈
            }
            cur = s.top();
            // 如果右子树存在且未被访问过, 则转向右子树
            if (cur->right != nullptr && cur->right != lastVisited) {
                cur = cur->right;
            } else {
                result.push_back(cur->val); // 访问根节点
                lastVisited = cur;
                s.pop();
                cur = nullptr;
            }
        }

        return result;
    }
};
Python （递归）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
from typing import List, Optional

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        self.postorder(root, result)
        return result

    def postorder(self, root: Optional[TreeNode], result: List[int]) -> None:
        if root is None:
            return
        self.postorder(root.left, result)  # 遍历左子树
        self.postorder(root.right, result) # 遍历右子树
        result.append(root.val)            # 访问根节点
Python （迭代）
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型一维数组
#
from typing import List, Optional

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        result = []
        stack = []
        curr = root
        last_visited = None               # 记录上一次访问的节点

        while curr or stack:
            while curr:
                stack.append(curr)
                curr = curr.left          # 左子树入栈
            curr = stack[-1]
            # 如果右子树存在且未被访问过，则转向右子树
            if curr.right and curr.right != last_visited:
                curr = curr.right
            else:
                result.append(curr.val)   # 访问根节点
                last_visited = curr
                stack.pop()
                curr = None               # 避免重复访问左子树

        return result

3、复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：递归方法为 O(n)（最坏情况），迭代方法同样为 O(n)。