145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note:
Recursive solution is trivial, could you do it iteratively?
Solution: Recursive
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
vals = []
if root:
vals.extend(self.postorderTraversal(root.left))
vals.extend(self.postorderTraversal(root.right))
vals.append(root.val)
return vals
Solution: Iterative
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
vals = []
stack = []
node = None
while stack or root:
if root:
stack.append(root)
root = root.left
elif stack[-1].right and stack[-1].right != node:
root = stack[-1].right
else:
node = stack.pop()
vals.append(node.val)
return vals