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].
Note: Recursive solution is trivial, could you do it iteratively?
Solution:
递归解法很简单：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param {TreeNode} root
# @return {integer[]}
def preorderTraversal(self, root):
if root == None:
return []
else:
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
迭代版本也是常规的将递归改成迭代的版本：
用一个栈来模拟递归的过程，注意栈 FILO 的特点。所以，对于当前根，要把右子树先加入栈，然后再把左子树加入栈。
前序遍历的顺序是：根 - 左子树 - 右子树。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param {TreeNode} root
# @return {integer[]}
def preorderTraversal(self, root):
stack = []
path = []
if root != None:
stack.append(root)
while stack != []:
e = stack.pop()
path.append(e.val)
if e.right != None:
stack.append(e.right)
if e.left != None:
stack.append(e.left)
return path