[Leetcode] Binary Tree Preorder Traversal

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].

Preorder: root - left - right. When thinking about the stack property (first in, last out), we want to push right child before the left child, so that eventually we will access left child first.

This problem is really neat, letting me see more clearly the difference between BFS (using queue) and DFS (stack). Indeed, the structure of the program below is the same as BFS, except that we used a stack here.

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

# 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] """ if not root: return [] stack = [root] res = [] while stack: node = stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res