Title: Binary Tree Postorder Traversal Source: leetcode.com
Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
|
1 2 3 4 5 |
1 \ 2 / 3 |
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
Python solution (Iterative)
|
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 29 30 31 32 33 34 35 36 37 38 39 40 |
''' https://leetcode.com/problems/binary-tree-postorder-traversal/ ''' # 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 not root: return [] stack = [root] visited = [False] res = [] while stack: node = stack.pop() flag = visited.pop() if flag: res.append(node.val) continue if not(node.left or node.right): res.append(node.val) continue stack.append(node) visited.append(True) if node.right: stack.append(node.right) visited.append(False) if node.left: stack.append(node.left) visited.append(False) return res |
Python solution (Recursive)
|
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 29 30 31 32 33 |
''' https://leetcode.com/problems/binary-tree-postorder-traversal/ ''' # 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 __init__(self): self.res = [] def helper(self, root): if not root: return if not (root.left or root.right): self.res.append(root.val) return if root.left: self.helper(root.left) if root.right: self.helper(root.right) self.res.append(root.val) def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ self.helper(root) return self.res |