## 题目描述：

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

```For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].```

Note: Recursive solution is trivial, could you do it iteratively?

## Python代码：

### 方法一（Accepted 43ms）

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

class Solution:
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
if root is None:
return []
stack = [root]
ans = []
pre = None
while stack:
cur = stack[-1]
if pre is None or pre.left == cur or pre.right == cur:
if cur.left:
stack.append(cur.left)
elif cur.right:
stack.append(cur.right)
elif pre == cur.left and cur.right:
stack.append(cur.right)
else:
ans.append(cur.val)
stack.pop()
pre = cur
return ans
``````

### 双栈法（Accepted 63ms）

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

class Solution:
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
if root is None:
return []
stack = [root]
ans = []
while stack:
top = stack.pop()
ans.append(top.val)
if top.left:
stack.append(top.left)
if top.right:
stack.append(top.right)
return ans[::-1]
``````

Pingbacks已关闭。