力扣145题：二叉树的后序遍历, 解题思路与C++实现

题目介绍

力扣第145题要求实现一个函数，该函数接收一个二叉树的根节点，并返回该树的后序遍历结果。后序遍历是一种遍历二叉树的算法，其顺序为：先遍历左子树，是右子树，是根节点。

解题思路分析

解题时，我们可以使用递归或迭代的方法。递归方法较为直观，但可能导致栈溢出。迭代方法可以使用栈来模拟递归过程，避免栈溢出的问题。

递归方法的核心在于递归地访问左子树和右子树，访问根节点。迭代方法则需要两个栈来存储遍历过程中的节点，一个用于模拟递归的顺序，另一个用于存储遍历结果。

递归方法实现

以下是使用递归方法实现的C++代码。递归方法简单易懂，但需要注意递归深度限制。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode root) {
        vector<int> result;
        postOrder(root, result);
        return result;
    }

    void postOrder(TreeNode node, vector<int>& result) {
        if (!node) return;
        postOrder(node->left, result);
        postOrder(node->right, result);
        result.push_back(node->val);
    }
};

迭代方法实现

以下是使用迭代方法实现的C++代码。这种方法使用两个栈来模拟递归过程，避免了递归深度限制的问题。

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