⭐算法OJ⭐二叉树的后序遍历【树的遍历】（C++实现）Binary Tree Postorder Traversal

⭐算法OJ⭐二叉树的中序遍历【树的遍历】（C++实现）Binary Tree Inorder Traversal
⭐算法OJ⭐二叉树的前序遍历【树的遍历】（C++实现）Binary Tree Preorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]

Explanation:

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

递归解法

• 后序遍历的顺序是：左子树 $\to$ 右子树 $\to$ 根节点。
• 使用递归实现。

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result; // 存储遍历结果
        postorder(root, result); // 递归遍历
        return result;
    }

private:
    void postorder(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return; // 递归终止条件
        }
        postorder(node->left, result); // 遍历左子树
        postorder(node->right, result); // 遍历右子树
        result.push_back(node->val); // 访问根节点
    }
};

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：$O(h)$，其中 $h$ 是二叉树的高度。递归调用栈的深度取决于树的高度。

迭代解法（使用栈）

• 使用 栈 模拟递归过程。
• 每次从栈中弹出一个节点，将其值插入结果列表的开头。
• 先压入左子树，再压入右子树，以确保右子树先被处理。从根节点开始，先将所有左子节点入栈，然后访问节点，再转向右子树。

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) {
            return result;
        }
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            result.insert(result.begin(), node->val); // 将节点值插入结果的开头
            if (node->left) {
                stk.push(node->left); // 先压入左子树
            }
            if (node->right) {
                stk.push(node->right); // 再压入右子树
            }
        }
        return result;
    }
};