# 145. 二叉树的后序遍历

<https://leetcode-cn.com/problems/binary-tree-postorder-traversal/>

## 解法一：递归

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.travel(root, res)
        return res

    def travel(self, root, res):  #辅助函数，注意要将结果集作为参数传入，才能在递归中修改结果集
        if root:            
            self.travel(root.left, res)                   
            self.travel(root.right, res)
            res.append(root.val)
```

## 解法二：用栈。

左右中的顺序，关键是判断左右是否已访问，且是先左后右，才能访问中。用cur表示当前访问，last表示上一次访问。

初始将根放入栈，last初始为根

每次令cur为当前栈顶，但是不弹栈

1）若cur左子非空，且cur左子和右子都不为last，则cur的左子入栈。解释：last是最近弹栈并输出的节点，若last等于cur的左子或右子，说明cur的左子树和右子树都已输出，此时不应将cur的左子入栈。否则说明左子树还没处理，将cur的左子入栈

2）若1不成立，且cur的右子非空，last不为cur的右子，则cur的右子入栈。解释：若last为cur的右子，说明cur的右子已输出，此时不应再将cur的右子入栈，否则说明右子树还没处理，要将cur的右子入栈

3）若1和2都不成立，说明cur的左子和右子都已输出，则将cur弹栈，并将cur标记为last

```python
class Solution:
    def postorderTraversal(self, root: TreeNode) :
        res = []
        last = root  #记录上一个访问节点，初始为根
        if not root:
            return res
        s = [root]
        while s:
            # 取栈顶作为本轮的根节点，注意最后才访问所以不能出栈
            cur = s[-1]
            # 1. c的左子非空，且左子和右子都没处理过
            if cur.left and cur.left != last and cur.right != last:
                s.append(cur.left)
            # 2. 若1不成立，且c的右子非空，且右子未处理过
            elif cur.right and cur.right != last:
                s.append(cur.right)
            # 3. 若1和2不成立，说明c的左子树和右子树都已处理，将cur弹栈并输出，last标记为cur
            else:
                cur = s.pop()
                res.append(cur.val)
                last = cur
        return res
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/1-200/145.-er-cha-shu-de-hou-xu-bian-li.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.