刷题——二叉树的后续遍历

方法一：双指针法

 void  postorder(TreeNode* root, vector<int>&res)
    {
            if(root == NULL) return;
            postorder(root->left,res);
            postorder(root->right,res);
            res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
           vector<int>res;
           postorder(root, res);
           return res;
    }

方法二：入栈出栈法

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* prev = nullptr; // 用于跟踪上一个访问的节点

    while (root != nullptr || !s.empty()) {
        while (root != nullptr) {
            s.push(root);
            root = root->left; // 先尽可能遍历到最左边
        }
        root = s.top(); // 获取当前栈顶元素（最深的未完全访问的节点）
        
        // 检查是否可以访问当前节点（即其右子树已访问或无右子树）
        if (root->right == nullptr || root->right == prev) {
            res.push_back(root->val); // 访问当前节点
            prev = root; // 更新prev为当前节点，表示其左右子树均已处理
            s.pop(); // 弹出当前节点，准备处理下一个
            root = nullptr; // 重置root，将在下次循环中从栈中获取新的节点
        } else {
            // 如果当前节点的右子树还未访问，则转向访问右子树
            root = root->right;
        }
    }
    return res;
}