DFS
- Non-recursion (use stack)
- Recursion （自己调用自己）
-- Traversal
-- Divide and Conquer
Binary Tree
Preorder: 根左右
Inorder：左根右
Postorder：左右根
Preorder
# 1. Non-recursion
# 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]
"""
res = []
stack = [root]
while stack:
node = stack.pop()
if node:
res.append(node.val)
stack.append(node.right) #注意：先压右！
stack.append(node.left) #压左
return res
-----------------------------
# 2. Traversal
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = []
# 4. 递归的调用
self.Tranversal(root, result)
return result
# 1. 递归的定义：把root为根的preoder加入到result中
def Tranversal(self, root, result):
# 3.递归的出口
if root == Null:
return
# return为空，表示该根左traversal函数已经到头，且没有返回值，进入还有运行的根右Traversal函数
# 2.递归的拆解
result.append(root.val) #根压栈
self.Tranversal(root.left, result) #根左
self.Tranversal(root.right, result) #根右
---------------------------------------------------------------
# 3. divice and conqure
class Solution(object):
# 1）递归的函数定义：返回以root为根的二叉树preorder
def preorderTraversal(self, root):
result = []
if not root:
return result #basis problem（递归最底层）结束条件
# 2) divide
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
# 3) conqure(merge)
result.append(root.val)
result = result + left + right
#子问题解决后返回值
return result
小结：
2\3区别：return value有没有
2:共享了同一个result 3:每一层递归都会有新的result
2\3相同: 都是递归，调用自己函数
