Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Python3
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution:
- def postorderTraversal(self, root):
- """
- :type root: TreeNode
- :rtype: List[int]
- """
- # approach: use iteration
- stack = []
- result = []
- current = root
- while current or len(stack):
- # push right children if it exists then current root
- # then down to left children
- while current:
- if current.right:
- stack.append(current.right)
- stack.append(current)
- current = current.left
- node = stack.pop()
- # for current root, its right children havenโt be handled
- # then handle right children first and then current root
- # by popping right children out and pushing current root back
- if len(stack) and node.right == stack[-1]:
- current = stack.pop()
- stack.append(node)
- else:
- result.append(node.val)
- return result
Add Comment
Please, Sign In to add comment