leetcode145. 二叉树的后序遍历，递归法+迭代法，全过程图解+步步解析，一点点教会你迭代法后序遍历

leetcode145. 二叉树的后序遍历，递归法+迭代法

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

递归法还是一如既往的简单。

postorder函数是递归函数，用于辅助实现后序遍历。它接收两个参数：一个指向当前节点的指针root和一个用于存储遍历结果的向量res。函数首先检查当前节点是否为空，如果是，则直接返回。如果不为空，则递归调用自身，先遍历左子树，再遍历右子树。在遍历完左右子树后，将当前节点的值添加到结果向量res中。

postorderTraversal函数是对外提供的公共接口，用于获取二叉树的后序遍历结果。它接收一个参数：一个指向二叉树根节点的指针root。函数首先初始化一个空的结果向量res，然后调用postorder函数进行后序遍历，并将遍历结果存储在res中。遍历完成后，返回这个结果向量。

整个实现过程是典型的递归方法，通过递归调用自身来遍历二叉树的每一个节点。递归的终止条件是当前节点为空，这时函数会返回而不执行任何操作。

class Solution {
public:
    void postorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二叉树后序遍历的迭代法相对前序和中序来说就要难一点了，

定义辅助栈：使用一个stack<TreeNode *>类型的栈stk来辅助遍历。

定义前一个访问节点：定义一个TreeNode *类型的指针prev，用来记录上一个被访问的节点。

迭代遍历：使用一个while循环，条件是root不为空或栈stk不为空。这个循环将一直执行，直到所有节点都被访问。

向左下推：内部的第一个while循环将root沿着左子树一直推到最底部，直到遇到空节点。每次迭代，都将当前节点压入栈中，并更新root为当前节点的左子节点。

处理当前节点：当左子树被完全遍历后，root将变为nullptr，此时从栈中弹出栈顶元素，即当前节点。

后序遍历条件判断：
如果当前节点的右子节点为空，或者右子节点已经访问过（即root->right == prev），则将当前节点的值添加到结果向量res中，并将prev更新为当前节点，然后将root设置为nullptr，准备处理下一个节点。
如果当前节点的右子节点不为空且未访问过，则将当前节点再次压入栈中，并更新root为当前节点的右子节点，继续遍历右子树。

1.我们再以这个图为例，首先向左下推直到D，ABD都入栈了，这时候判断D的左子树为null，于是弹出栈顶D，D没有右子树，于是D首先被遍历进结果数组，并将前一个访问节点记录为D，将root变成null，方便处理下一个节点。

2.接下来弹出栈顶元素B，B有右节点且前一个访问节点不是B的右节点，所以把B再推入栈，访问B的右节点F。

3.F有左节点，于是F入栈,E入栈，E没有左节点，E出栈。E也没有右节点，于是E第二个被遍历进结果数组，并将前一个访问节点记录为E，将root变成null，方便处理下一个节点。

4.再弹出栈顶元素F，F没有右节点，于是F第三个被遍历进结果数组，并将前一个访问节点记录为F，将root变成null，方便处理下一个节点。

5.再弹出栈顶元素B，B有右节点，但是！！前一个访问节点是B的右节点F，所以B第四个被遍历进结果数组，并将前一个访问节点记录为B，将root变成null，方便处理下一个节点。

依此类推遍历完全部节点DEFBHGICA。
做完此题，二叉树的中序遍历就再简单不过了，可以秒杀。
具体题目如下。

我也写了二叉树中序遍历的题解，可以去看看。相对二叉树的中序遍历，后序遍历的迭代法确实难了不少，值得反复学习。