DFS

• Non-recursion (use stack)
• Recursion （自己調(diào)用自己）
  -- 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. 遞歸的調(diào)用
        self.Tranversal(root, result)
        return result

    # 1. 遞歸的定義：把root為根的preoder加入到result中
    def Tranversal(self, root, result):
        # 3.遞歸的出口
        if root == Null:
            return   
 # return為空，表示該根左traversal函數(shù)已經(jīng)到頭，且沒(méi)有返回值，進(jìn)入還有運(yùn)行的根右Traversal函數(shù)
        
        # 2.遞歸的拆解
        result.append(root.val)  #根壓棧
        self.Tranversal(root.left, result) #根左
        self.Tranversal(root.right, result)  #根右

---------------------------------------------------------------
# 3. divice and conqure
class Solution(object): 
# 1）遞歸的函數(shù)定義：返回以root為根的二叉樹(shù)preorder 
    def preorderTraversal(self, root):
        result = []
        if not root:
            return result #basis problem（遞歸最底層）結(jié)束條件
        # 2) divide
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)

        # 3) conqure(merge)
        result.append(root.val)
        result = result + left + right
        #子問(wèn)題解決后返回值
        return result 

小結(jié)：
2\3區(qū)別：return value有沒(méi)有
2:共享了同一個(gè)result 3:每一層遞歸都會(huì)有新的result
2\3相同: 都是遞歸，調(diào)用自己函數(shù)