I wrote post Binary_Tree_Traversal around two years ago to help me remember how to traversal binary tree iteratively. The solution in that post is quite simply. But I still have trouble to remember it since the code pattern is slight different within preorder, inorder, postorder.
Eventually, I rewrite the code using similar pattern in python.
preorder
1 2 3 4 5 6 7 8 9 10 11
classSolution(object): defpreorderTraversal(self, root): rst, stack = [], [] cur = root while cur or stack: while cur: rst.append(cur.val) stack.append(cur.right) cur = cur.left cur = stack.pop() return rst
inorder
1 2 3 4 5 6 7 8 9 10 11 12
classSolution: definorderTraversal(self, root: TreeNode) -> List[int]: rst, stack = [], [] cur = root while cur or stack: while cur: stack.append(cur) cur = cur.left cur = stack.pop() rst.append(cur.val) cur = cur.right return rst
postorder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution: defpostorderTraversal(self, root: TreeNode) -> List[int]: rst, stack = [], [] cur = root while cur or stack: while cur: stack.append(cur) cur = cur.left or cur.right cur = stack.pop() rst.append(cur.val) if stack and stack[-1].left == cur: cur = stack[-1].right else: cur = None return rst