Given a binary tree, return the postorder traversal of its nodes' values.
Example 1
Given binary tree [1,null,2,3],
1
\
2
/
3
return [3,2,1]
Solution 1: recursive
# 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 = []
self.dfs(root, ret)
return ret
def dfs(self, root, ret):
if root:
self.dfs(root.left, ret)
self.dfs(root.right, ret)
ret.append(root.val)
Solution 2: iteratively (my solution, easy to understand)
use stack to store node value, right child, and left child repeatedly. When node value is popped out, add to result, otherwise repeat.
# 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]
"""
stack = [root]
ret = []
while stack:
node = stack.pop()
if type(node) == int:
ret.append(node)
elif node:
stack.append(node.val)
stack.append(node.right)
stack.append(node.left)
return ret
Another version, popular online
return node value -> right child -> left child repeatedly, and then reverse the result.
# 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]
"""
if root is None:
return []
stack = [root]
ret = []
while stack:
node = stack.pop()
ret.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ret[::-1]
Another version, hard to understand
# 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]
"""
if root is None:
return []
stack = [root]
ret = []
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:
ret.append(cur.val)
stack.pop()
pre = cur
return ret