bfs

[chenicks]

dfs 深度優先;遞歸 O(3n) -> O(n)

Preorder Traversal

/內存使用較少，空間使用較少/

template

1. base case

   以下順序可以交換

   • do something
   • recurse for subproblems

要相信自己的 recurse pre(先打印在遞歸)/in(夾在中間)/post order(先左後右再打印, root 最後打印)

top down vs bottom up

top down dfs

• 把值通過參數的形式從上往下傳
• 一般 dfs 本身不返回值

bottom up dfs (難也更常見)

• 把值從下(subproblem)往上傳
• 當前遞歸層利用 subproblem 傳上來的值計算當前層的新值並且返回
• 一定會有返回值

bottom up dfs

step:

1. base case
2. 向子問題要答案(return value)
3. 利用子問題的答案構建當前問題(當前遞歸層)的答案
4. 有必要，做一些和外操作
5. 返回答案(給父問題)

104

124

top down

1. base case
2. 利用父問題傳下來的值來做一些計算
3. 有必要做些額外操作
4. 把值傳下去給子問題繼續遞歸

129

相關例題

98. vakudate binary search tree
99. balanced binary tree
100. path sum II
101. lowest common ancestor of a binary tree
102. delete node in a bst
103. most frequency subtree sum

[chenicks]

Tree

110 Balanced Binary Tree DFS (Tree) Tree Python

226 Invert Binary Tree DFS (Tree) Tree Python

572 Subtree of Another Tree DFS (Tree) Tree Python

105 Construct Binary Tree from Preorder and Inorder Traversal DFS (Tree) Tree Python

112 Path Sum DFS (Tree) Python

113 Path Sum II DFS (Tree) Tree Python

235 Lowest Common Ancestor of a Binary Search Tree DFS (Tree) Tree Python

236 Lowest Common Ancestor of a Binary Tree DFS (Tree) Tree Python

重要題型

257 Binary Tree Paths DFS (Tree) Tree Python

[Lint] 474 Lowest Common Ancestor II DFS (Tree) Tree Python

[Lint] 578 Lowest Common Ancestor III DFS (Tree) Tree Python

[Lint] 596 Minimum Subtree DFS (Tree) Tree Python

543 Diameter of Binary Tree DFS (Tree) Python

144 Binary Tree Preorder Traversal DFS (Tree) Tree Python 內含 處理 Tree 樹問題的重點

145 Binary Tree Postorder Traversal DFS (Tree) Tree Python

114 Flatten Binary Tree to Linked List DFS (Tree) Tree Python

[chenicks]

104

bottom up

1. base case
2. 向子問題要答案 (max depth)
3. 利用子問題的答案構建當前問題(當前遞歸層)的答案 max(left_ans, right_ans) + 1
4. 若有必要，做一些額外操作
5. 返回答案(給父問題) return depth

6. def maxDepth(root):
   if not root:
       return 0
   left = maxDepth(root.left)
   right = maxDepth(root.right)
   max_depth = max(left, right) + 1
   return max_depth

124

step:

1. base case
2. 向子問題要答案(return value) > (max sum root to leaf path)
3. 利用子問題的答案構建當前問題(當前遞歸層)的答案 max(left, right, 0) + node.val
4. 若有必要，做一些額外操作 global_max = max(left, 0) + max(right, 0) + node.val
5. 返回答案 (給父問題) return ans

def maxPathSum(root):
    maxs = globals()
    def dfs(node):
        if node == None:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        left = 0 if left < 0 else left
        right = 0 if right < 0 else right
        maxs = max(maxs, left + right + node.val)
        return max(left + node.val, right + node.val)  
    dfs(root)
    return maxs   

129

1. base case(leaf); global_sum += num
2. 利用父問題傳下來的值做一些計算 concat digits -> num = num *10 +node.val
3. 有必要做一些額外操作
4. 把值傳下去給子問題繼續遞歸 dfs(child_node, num)

def sumNumbers(root):
    if not root:
        return 0

    sums = 0
        def dfs(root, num):
        num = num * 10 + root.val
        if not root.left and not root.right:
            sums += num
            return
        if root.left != None:
            dfs(root.left, num)
        if root.right != None:
            dfs(root.right, num)

    dfs(root, 0)
    return sums

[chenicks]

200

def numIslands(grid):
    def dfs(row, col):
        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == '0':
            return
        # 標記為已訪問過的陸地
        grid[row][col] = '0'

        # 遞歸搜索上下左右四個方向
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)
    if not grid or not grid[0]:
        return 0

    num_rows, num_cols = len(grid), len(grid[0])
    count = 0
    for row in range(num_rows):
        for col in range(num_cols):
            if grid[row][col] == '1':
                # 遇到新的島嶼，進行深度優先搜索
                dfs(row, col)
                count += 1
    return count

if __name__ == '__main__':
    grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["1","1","0","0","0"],
        ["0","0","0","0","0"]
    ]
    print(numIslands2(grid))

[chenicks]

547

def findCircleNum(isConnected):
    visited = [False] * len(isConnected)
    count = 0
    def dfs(i):
        visited[i] = True
        print(f" i >> {i}, {visited}")
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1 and not visited[j]:
                dfs(j)
     for i in range(len(isConnected)):
        print(i, visited, count)
        if not visited[i]:
            dfs(i)
            count += 1
        print('-----')

    return count

if __name__ == '__main__':
    # testCase1
    isConnected = [[1,1,0],[1,1,0],[0,0,1]]
    print(findCircleNum(isConnected))

[chenicks]

def strokesRequired(picture):
    def dfs(picture, visited, i, j, color):
        # 設定返回
        if i < 0 or i >= len(picture) or j < 0 or j >= len(picture[0]):
            return
        # 如果顏色不同返回
        if visited[i][j] or picture[i][j] != color:
            return
        # 先設定搜尋
        visited[i][j] = True
        # 上下左右
        dfs(picture, visited, i+1, j, color)
        dfs(picture, visited, i-1, j, color)
        dfs(picture, visited, i, j+1, color)
        dfs(picture, visited, i, j-1, color)

    # 先知道長寬
    rows = len(picture)
    cols = len(picture[0])
    # 設定是否有看過
    visited = [[False] * cols for _ in range(rows)]
    # 幾種顏色
    count = 0
    # 開始遍歷
    for i in range(rows):
         for j in range(cols):
            # 如果沒搜尋過
            if not visited[i][j]:
                # 取得顏色
                color = picture[i][j]
                # 開始搜尋前後左右，給 picture, visited, 目前位置與顏色
                dfs(picture, visited, i, j, color)
                count += 1
    return count

picture = ["aabba", "aabba", "aaacb"]
print(strokesRequired(picture))