145.二叉树的后序遍历

难度：容易

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

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

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

**进阶：**递归算法很简单，你可以通过迭代算法完成吗？

递归算法

递归算法的三个要素：

确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

每次写递归，都按照这三要素来写，可以保证写出正确的递归算法！

以前序遍历为例：

确定递归函数的参数和返回值：因为要打印出后序遍历节点的数值，所以参数里需要传入 result 来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是 void，代码如下：
java
```
void postorder(TreeNode root, List<Integer> result)
```
确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点为空，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：
java
```
if (root == null) {
    return;
}
```
确定单层递归的逻辑：后序遍历是左右中的循序，所以在单层递归的逻辑，要最后取中节点的数值，代码如下：
java
```
postorder(root.left, result);  // 左
postorder(root.right, result); // 右
result.add(root.val);          // 中
```

单层递归的逻辑就是按照左右中的顺序来处理的，这样二叉树的后序遍历，基本就写完了。

代码展示

java

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
}

public void postorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

迭代法

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归可以返回上一层位置的原因。

那么我们也可以用迭代的方式实现递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同。

先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，使其变成中右左的遍历顺序，然后再反转 result 数组，输出的结果顺序就是左右中了。

代码原理：

创建辅助栈和结果列表：定义一个栈 stack 用于存放将要访问的节点，和一个列表 result 用于存储遍历的结果。
初始化栈：如果根节点 root 不为 null，将它压入栈中。
迭代遍历：使用一个 while 循环来迭代遍历树，只要栈不为空，就继续循环。
访问节点：在每次循环中，从栈中弹出一个节点，将它的值添加到结果列表中。
压入左孩子和右孩子：如果弹出节点的左孩子存在，将左孩子压入栈中。然后，如果右孩子存在，也将右孩子压入栈中。这样做是因为栈是后进先出的结构，我们希望先处理右孩子，所以右孩子后压入栈。
反转结果列表：在遍历结束后，将结果列表 result 反转。这是因为按照上述过程，我们实际上得到的是根-右-左的顺序，而后序遍历的正确顺序应该是左-右-根。反转列表正好得到正确的顺序。

代码展示

java

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();

    if (root == null) {
        return result;
    }

    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);

        // 因为栈是后进先出，所以先压左孩子
        if (node.left != null) {
            stack.push(node.left);
        }
        // 后压右孩子
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    Collections.reverse(result);
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

总结

迭代法比递归法更难想到。

145.二叉树的后序遍历 ​

递归算法 ​

代码展示 ​

迭代法 ​

代码展示 ​

总结 ​

145.二叉树的后序遍历

递归算法

代码展示

迭代法

代码展示

总结