Problem: 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?

Solution: Binary Tree Preorder Traversal, Python:

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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-31 22:52:37
# @Author : NSSimacer
# @Version : 1.0
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def preorderTraversal(self, root):
result = []
stack = [root]
while stack:
node = stack.pop()
if node:
result.append(node.val)
stack.append(node.right)
stack.append(node.left)
return result

用栈实现,时间复杂度O(N),空间复杂度O(N)。