# 144. Binary Tree Preorder Traversal

## 刷题内容

• https://leetcode.com/problems/binary-tree-preorder-traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?


## 解题方案

Recursive递归,瞬秒

class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
res.append(root.val)
if root.left:
res.extend(self.preorderTraversal(root.left))
if root.right:
res.extend(self.preorderTraversal(root.right))
return res


class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
res = []
self.preorder(root,res)
return res

def preorder(self,root,res):
if root == None:
return
res.append(root.val)
self.preorder(root.left,res)
self.preorder(root.right,res)


Iterative, 迭代

class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
stack = []
stack.append(root)

while(len(stack) > 0):
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res