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 = NoneclassSolution(object):defpostorderTraversal(self,root):""" :type root: TreeNode :rtype: List[int] """ ret = [] self.dfs(root, ret)return retdefdfs(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 = NoneclassSolution(object):defpostorderTraversal(self,root):""" :type root: TreeNode :rtype: List[int] """ stack = [root] ret = []while stack: node = stack.pop()iftype(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 = NoneclassSolution(object):defpostorderTraversal(self,root):""" :type root: TreeNode :rtype: List[int] """if root isNone: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 = NoneclassSolution(object):defpostorderTraversal(self,root):""" :type root: TreeNode :rtype: List[int] """if root isNone:return [] stack = [root] ret = [] pre =Nonewhile stack: cur = stack[-1]if pre isNoneor 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 = curreturn ret