https://leetcode.com/discuss/23326/very-simple-iterative-python-solution
Binary Tree Preorder Traversal
Total Accepted: 89130 Total Submissions: 240451 Difficulty: Medium
Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
Code
# 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 preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = [root]
res = []
while stack:
node = stack.pop()
if node:
res += [node.val]
stack.append(node.right)
stack.append(node.left)
return res
Idea
Preorder: [root], [left], [right]
So we use a stack to add right first then left. so whenever we pop an element out, the left element will always be popped out before the right element. Since we want to return preorder result, whenever an element is popped out, we add it to `res` immediately.