leetcode144 -- Binary Tree Preorder Traversal (二叉树先根序遍历)

# 小郑之家~

### 题目

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

Example:

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

Output: [1,2,3]



### 法一，递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:

res =[]
self.preorder(root, res)
return res

def preorder(self, root, res):
if not root:
return

res.append(root.val)
self.preorder(root.left, res)
self.preorder(root.right, res)



### 非递归的方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:

if not root:
return []
res = []
stack = [root]

while len(stack)>0:
t = stack.pop()
res.append(t.val)

if t.right:
stack.append(t.right)   # 因为先放进去的会后使用，所以要先把右子节点放进去.
if t.left:
stack.append(t.left)

return res



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:

if not root:
return []
res = []
stack = []

p = root
while len(stack)>0 or p:
if p:
stack.append(p)
res.append(p.val)
p = p.left
else:
t = stack.pop()
p = t.right
return res