# 145. Binary Tree Postorder Traversal

{% embed url="<https://leetcode.com/problems/binary-tree-postorder-traversal/>" %}

做Q106的时候就利用过`postorder`的这个性质：

> `postorder`本质就是逆序版的`right-first preorder`

{% content-ref url="106.-construct-binary-tree-from-inorder-and-postorder-traversal" %}
[106.-construct-binary-tree-from-inorder-and-postorder-traversal](https://xuqiangwen1994.gitbook.io/practice/106.-construct-binary-tree-from-inorder-and-postorder-traversal)
{% endcontent-ref %}

所以讨巧写法就是写个`right-first preorder`然后 reverse 就行。

或者按照`recursively`来写，也挺简单的。

麻烦的是`iteratively`地写，需要给 node 标记`visited state`，因为本质上是遍历了两遍`tree`，第一遍排出`traversal order`，第二遍获取值。

{% tabs %}
{% tab title="reversed right-first preorder" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root: return res
        stack = collections.deque([root])
        while stack:
            cur = stack.pop()
            res.append(cur.val)
            if cur.left: stack.append(cur.left)
            if cur.right: stack.append(cur.right)
        res.reverse()
        return res
```

{% endtab %}

{% tab title="recursively" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def postorder(node, res):
            if not node: return
            if node.left: postorder(node.left, res)
            if node.right: postorder(node.right, res)
            res.append(node.val)
        
        postorder(root, res)
        return res
```

{% endtab %}

{% tab title="iteratively" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        if not root: return res
        
        stack = collections.deque([(root, False)])
        while stack:
            node, visited = stack.pop()
            if visited: res.append(node.val)
            else:
                stack.append((node, True))
                if node.right: stack.append((node.right, False))
                if node.left: stack.append((node.left, False))

        return res
```

{% endtab %}
{% endtabs %}
