1.题目介绍

给定一个二叉树的根节点 root ，返回它的后序遍历。
示例 1：

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

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

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

提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

2.题解

2.1 递归

首先我们需要了解什么是二叉树的前序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。递归终止的条件为碰到空节点。

代码

//
// Created by trmbh on 2023-10-26.
// 145. 二叉树的后序遍历

#include<iostream>
#include<vector>
#include<string>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
                using namespace std;
        if (root == nullptr) return arr;
        else {
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            arr.push_back(root->val);
        }
        return arr;
    }
private:
    std::vector<int> arr;
};

int main(){
    Solution solution;
    TreeNode n1(3);
    TreeNode n2(2, &n1, nullptr);
    TreeNode n(1, nullptr,&n2);
    std::vector<int> arr = solution.inorderTraversal(&n);
    for (int num:arr){
        std::cout << num << ' ';
    }
}

2.2迭代

思路

在递归中，我们其实隐式地使用了栈来保存前面节点的信息；所以这里如果我们要使用迭代的方法的话，就应该使用显式栈来保存节点信息，并在返回时提供节点信息。

后序遍历的迭代算法比较复杂，实际上是一种（向左子树遍历到空节点-> 回退到根节点（过度） -> 遍历右子树 -> 回退到根节点（标记，出栈，入数组）），这里需要补充一个pre指针指向上一个刚遍历过的节点，防止重复遍历的发生。

首先是对于左子树的遍历，这里有两种情况，一种是尚未遍历过左子树的节点，那么遍历左子树直到节点为空为止；一种是该节点为上一次已经遍历过左右子树的节点，这种便跳过左子树遍历，继续回转到栈中存储的上一个节点。

之后是对于右子树的遍历，先利用栈中存储的信息，回退到根节点，之后取root->right即可.这里的root->right实际上又成为了新的根节点，再按照之前的方式遍历即可。

最后是对于根节点的输出，根节点必须满足自己的左右子树均被遍历过才可进行输出。此时有两种情况，该根节点的右子树为空或者右子树的根节点刚刚遍历过（被标记），此时我们便可以进行（标记，出栈，入数组）的一系列操作了。

整个大循环的结束时（栈空 + root == pre）由于栈空代表目前节点正是最初二叉树的根节点，而root == pre代表该节点的左右子树均遍历完毕，也就是整个二叉树后序遍历完毕！

举个简单的例子如下图所示

代码

class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode *root) {
        std::stack<TreeNode *> stk;
        std::vector<int> arr;
        TreeNode *pre = nullptr; //存储上一个刚遍历过的节点
        if (root == nullptr) {
            return arr;
        }
        while (!stk.empty() || root != pre) {
            // 遍历左子树
            while (root != nullptr && root != pre) {
                stk.push(root);
                root = root->left;
            }
            // 回退到上一个节点
            root = stk.top();

            // 遍历右子树
            root = root->right;

            /* 左右子树均遍历完毕*/
            if (root == nullptr || root == pre) {
                root = stk.top(); //回退到上个节点
                stk.pop(); //顺序出栈
                arr.push_back(root->val); //输出
                pre = root;//保存该节点，作为后续判断依据
            }
        }
        return arr;
    }
};