Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
1
2
3
4
5
6
| Given binary tree {1,#,2,3},
1
\
2
/
3
|
return [3,2,1].
Note:
Recursive solution is trivial, could you do it iteratively?
Solution
(Binary-Tree-Postorder-Traversal.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
ret = []
stack = []
if root == None:
return ret
stack.append(root)
while stack:
top = stack.pop()
ret.append(top.val)
if top.left:
stack.append(top.left)
if top.right:
stack.append(top.right)
return ret[::-1]
|