# LeetCode: 145. Binary Tree Postorder Traversal

## 题目¶

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

```Input: root = [1,null,2,3]
Output: [3,2,1]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = [1]
Output: [1]
```

Example 4:

```Input: root = [1,2]
Output: [2,1]
```

Example 5:

```Input: root = [1,null,2]
Output: [2,1]
```

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Recursive solution is trivial, could you do it iteratively?

## 解法¶

### 递归法实现后序遍历¶

```# 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):
nodes = []
self._postorder(nodes, root)
return nodes

def _postorder(self, nodes, root):
if root is None:
return

self._postorder(nodes, root.left)
self._postorder(nodes, root.right)
nodes.append(root.val)
```

### stack 法实现后序遍历¶

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def postorderTraversal(self, root):
if root is None:
return []

nodes = []
stack1 = []
stack2 = []

stack1.append(root)
while stack1:
curr = stack1.pop()
stack2.append(curr)
if curr.left is not None:
stack1.append(curr.left)
if curr.right is not None:
stack1.append(curr.right)

while stack2:
node = stack2.pop()
nodes.append(node.val)

return nodes
```