> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/shu/145-er-cha-shu-de-hou-xu-bian-li.md).

# \[145]\[困难] 二叉树的后序遍历

## 题目描述

[145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)

给定一个二叉树，返回它的 后序 遍历。

示例:

```
输入: [1,null,2,3]  
   1
    \
     2
    /
   3

输出: [3,2,1]
```

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

## 解题思路

### 递归

```python
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res
```

### 迭代

后续遍历顺序是**左右中**. 但如果我们按**中右左**的形式遍历, 得到的结果会与后续遍历的结果完全相反, 只需要将这种遍历方式得到的数组反转, 即得到后续遍历的结果.

前序遍历顺序是**中左右**, 与**中右左**相比只是先左和先右的问题, 参考[\[144\]\[中等\] 二叉树的前序遍历](/garnet/suan-fa/shu/144-er-cha-shu-de-qian-xu-bian-li.md)的迭代方法.

```python
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        res, stack = [], [root]
        while stack:
            node = stack.pop(-1)

            res.append(node.val)
            if node.left is not None:
                stack.append(node.left)
            if node.right is not None:
                stack.append(node.right)
        return res[::-1]
```