題目
紀錄一下一開始的思路，檢討錯誤，再整理最後的答案。一開始的想法：

1. 這應該可以分解成最小可重複動作，用遞迴解看看
2. 覺得可以用原本的 method 當遞迴函式，把 image, color 照樣傳入，sr, sc 為該點的座標
3. 最小可重複動作：從當下這點擴散到周圍四個點

題目
思路

1. 樹的問題會先從遞迴來想比較直觀，首先找出最小可重複動作來作為 recursive case
2. 先假設我們可以用題目給的 method 直接當作遞迴的函式，也就是說我們遞迴函式的回傳，是 preorder 排序的 node values
3. 最小可重複動作：對於我這個 node 來說，回傳 preordered values

1
2
3
4
5
6
7

def preorder(self, root: 'Node') -> List[int]:
    if not root:
        return []
    result = [root.val]
    for child in root.children or []:
        result.extend(self.preorder(child))
    return result

題目
思路

1. 樹的問題用遞迴來解相對上比較直覺，所以先試試遞迴解
2. 拆解到最小單位來找 recursive case: 隨機取樹中一個點，判斷它是否 valid
3. 大部分情況都會有上下限。以左邊的點為例，上限就是父節點的值，下限就是它所在的右子樹的父節點的值，所以這個值必須由上到下一層層傳遞下來。反之，右邊的點的話，就變成上限必須一層層傳遞下來
4. 因為上下限必須用傳遞的，所以寫一個 function node_valid 接受上下限的參數

題目
思路

1. 一次一層很直覺想到廣先搜尋 (BFS)，所以用 iterative 的做法來解
2. 一次迴圈處理一層，並把下一層節點放入 stack 繼續在下次迴圈處理
   • stack 也是 list of list, 裡面的每個 list 都是一層節點

題目
思路

1. Inorder Traversal: 對任意節點來說，順序為 左子樹 -> 自己 -> 右子樹
2. 可拆解為最小單位動作，即第一點，故使用遞迴

題目
思路

1. 跟 House Robber 很像，只差在房子的排列變成頭尾相連，有沒有辦法把這題拆解，變成能用上第一版 House Robber 的解題方法？譬如把環形變回直排？
2. 變成環形之後多出來的限制讓我們可以把這題分成以下三種情況：
   1. 搶第一個、不搶最後一個：加入第三種情況，等同於可以視為直排，但只考慮到倒數第二個
   2. 不搶第一個、搶最後一個：加入第三種情況，等同於可以視為直排，但從第二個開始考慮

快速解 (適用於遞迴函式內呼叫自己 > 1 次)

1. 看這個遞迴函式呼叫自己幾次，假設呼叫了 x 次
2. 看看這個函式的遞迴深度。也就是說這個函式的初始呼叫會需要經過幾次的呼叫自己才會再也沒有任何呼叫，每條路都停止在 base case (終止條件)
   • 舉例：可以先看看下面的詳細解，初始呼叫為 u_paths(0, 0)，此時 u_paths(i + 1, j) 需要呼叫 m 次才會停，u_paths(i, j + 1) 需要呼叫 n 次才會停，所以總共呼叫 m + n 次才會停，此時遞迴深度 h = m + n
3. 承上例，此時時間複雜度為 O(x^h)

• 至少目前套用在幾個比較單純的遞迴式都成立，不確定複雜的是不是也成立

題目
思路

1. 可以把得出答案的過程拆解為最小可重複步驟，用遞迴來解
2. Recursive case: 假設 index 為 i，由 index 0 搶到 i 可得的最大收穫為 inner_rob(i)。在位置 i, 可選擇搶或不搶：
   1. 不搶：最大收穫跟前一個點一樣，為 inner_rob(i - 1)
   2. 搶：代表前一個點一定是不搶，所以最大收穫為這個點的 money nums[i] 再加上前前個點的最大收穫 inner_rob(i - 2)
   • 所以 inner_rob(i) 為以上兩種情況取較大的那個

題目
思路

1. 每走一步都會是一個 unique path，到終點的路線是由每一步所組成的，所以可以用遞迴的方式來想，最小的可重複動作就是一步，點 (i, j) 到終點的 unique path count 就是 (i + 1, j) 和 (i, j + 1) 的 unique path count 的和

2. 最小可重複動作 return u_paths(i + 1, j) + u_paths(i, j + 1)

題目

做法一：recursive - DFS

1. 找出最小的可重複動作：merge 兩個 nodes

   • 題目給的 method 就可以用來做遞迴

2. 假設 mergeTrees 已完成，實作此最小可重複動作

   1 2 3 4

   root1.val += root2.val root1.left = self.mergeTrees(root1.left, root2.left) root1.right = self.mergeTrees(root1.right, root2.right) return root1