LeetCode 2024/02/21-2024/02/29 每日一題

每日第1題為中文站(LCCN) ，第2題為英文站(LCUS) ，題目連結皆統一為英文站的題目連結。
Easy 、Medium 、Hard 難度的題目分別用🟢🟡🔴表示。
若為周賽題目會額外標註由 @zreotrac 零神計算的rating分數。

All problems solved by python

---

2024-02-21

🟡 106. Construct Binary Tree from Inorder and Postorder Traversal

題意

• 給定兩個整數陣列 $inorder$ 和 $postorder$ ，其中 $inorder$ 是二元樹的 中序(inorder)遍歷， $postorder$ 是同一棵樹的 後序(postorder)遍歷 。
• 依照給定的 $inorder$ 和 $postorder$ ，構造出二元樹並返回其根節點 $root$ 。

思路：遞迴(Recursion)

• $inorder$ 和 $postorder$ 可以構建出唯一 的Binary Tree，postorder 的最後一個元素 為根節點，並且它將 inorder 分為左右兩個子樹。
• 對於給定的 $inorder$ 和 $postorder$ ，我們可以使用遞迴的方式來構建二叉樹，具體步驟如下：
  1. $root$ 是 $postorder$ 的最後一個元素，並且它將 $inorder$ 分為左右兩個子樹。
  2. 因此可以找到 $root$ 在 $inorder$ 中的位置 $idx$ ，且 $idx$ 同時也是左子樹的大小。
  3. 遞迴構建左右子樹。
     • 左子樹：$inorder[:idx]$ 和 $postorder[:idx]$
     • 右子樹：$inorder[idx+1:]$ 和 $postorder[idx:n-1]$
• 時間複雜度：$O(n^2)$，其中 $n$ 為二叉樹的節點數，每次查找 $root$ 在 $inorder$ 中的位置需要 $O(n)$ 的時間。
• 空間複雜度：$O(n^2)$，最壞情況下，每次遞迴都需要 $O(n)$ 的空間。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        n = len(postorder)
        if n == 0:
            return None
        root = TreeNode(postorder[-1])
        idx = inorder.index(postorder[-1]) # root index in inorder, also the size of left subtree
        root.left = self.buildTree(inorder[:idx], postorder[:idx])
        root.right = self.buildTree(inorder[idx+1:], postorder[idx:n-1])
        return root

---

🟡 201. Bitwise AND of Numbers Range

題意

• 給定兩個整樹 $left$ 和 $right$ ，表示區間 $[left, right]$ ，返回此區間內所有數字 按位與(bitwise AND) 的結果（包含 $left$ 、$right$ ）。

思路：位運算(Bit Manipulation)

• 因為 $left$ 和 $right$ 之間的數字，其二進制表示中的某些位一定會有不同的部分，所以只需要考慮 $left$ 和 $right$ 的前綴共同部分即可。

方法一：位移

• 逐位右移 $left$ 和 $right$ 直到 $left$ 和 $right$ 相等，並記錄右移的次數 $n$ ，最後將 $left$ 左移 $n$ 位即為答案。
• 時間複雜度：$O(\log r)$，其中 $r$ 為 $right$ 的值。
• 空間複雜度：$O(1)$。

方法二：Brian Kernighan Algorithm

• 透過 $x \& (x-1)$ 可以消除 $x$ 的最低位的 $1$ ，所以我們可以逐位消除 $right$ 的最低位的 $1$ ，直到 $right <= left$ 。
• 時間複雜度：$O(\log r)$，其中 $r$ 為 $right$ 的值。
• 空間複雜度：$O(1)$。

位移Brian Kernighan

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        n = 0
        while left != right:
            left >>= 1
            right >>= 1
            n += 1
        return left << n

class Solution:
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        while left < right:
            right = right & (right - 1) # 消除最低位的1
        return right

---

2024-02-22

🟡 889. Construct Binary Tree from Preorder and Postorder Traversal 1732

題意

• 給定兩個整數陣列 $preorder$ 和 $postorder$ ，其中 $preorder$ 是二元樹的 前序(preorder)遍歷， $postorder$ 是同一棵樹的 後序(postorder)遍歷 。
• 依照給定的 $preorder$ 和 $postorder$ ，構造出二元樹並返回其根節點 $root$ ，如果存在多個答案，則返回其中任何一個。

思路：遞迴(Recursion)

• $preorder$ 和 $postorder$ 構建出的Binary Tree 不一定唯一 ，但是可以確定的是，$preorder$ 的第一個元素 為根節點，並且其為 $postorder$ 的最後一個元素 。
• 對於給定的 $preorder$ 和 $postorder$ ，我們可以使用遞迴的方式來構建二叉樹，具體步驟如下：
  1. 令左子樹的根節點 $left$ 為 $preorder[1]$ ，並且它將 $postorder$ 分為左右兩個子樹。(但包含於左子樹)
  2. 因此可以找到 $left$ 在 $postorder$ 中的位置 $idx$ ，且左子樹的大小為 $idx+1$。
  3. 去除根節點，遞迴構建左右子樹。
     • 將 $preorder[1:idx+2]$ 和 $postorder[:idx+1]$ 作為左子樹的 $preorder$ 和 $postorder$ ，遞迴構建左子樹。
     • 將 $preorder[idx+2:]$ 和 $postorder[idx+1:n-1]$ 作為右子樹的 $preorder$ 和 $postorder$ ，遞迴構建右子樹。
• 時間複雜度：$O(n^2)$，其中 $n$ 為二叉樹的節點數，每次查找 $left$ 在 $postorder$ 中的位置需要 $O(n)$ 的時間。
• 空間複雜度：$O(n^2)$，最壞情況下，每次遞迴都需要 $O(n)$ 的空間。

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        n = len(postorder)
        if n == 0:
            return None
        root = TreeNode(preorder[0])
        if n == 1:
            return root
        idx = postorder.index(preorder[1]) # let preorder[1] be the root of left subtree, then find the index of preorder[1] in postorder
        root.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1]) # size of left subtree is idx+1
        root.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:n-1])
        return root

---

🟢 997. Find the Town Judge 1202

題意

• 在一個小鎮裡有 $n$ 個人，依照從 $1$ 到 $n$ 的順序編號。
• 這些人中可能有一個人是小鎮法官，如果小鎮法官真的存在，那麼：
  1. 小鎮法官不會信任任何人。
  2. 每個人（除了小鎮法官）都信任這位小鎮法官。
  3. 只有一個人同時滿足屬性 1 和屬性 2 。
• 給定一個陣列 $trust$ ，其中 $trust[i] = [a_i, b_i]$ 表示編號為 $a_i$ 的人信任編號為 $b_i$ 的人。
• 如果小鎮法官存在並且可以確定他的身份，請返回該法官的編號；否則返回 $-1$ 。

思路：圖論(Graph)

• 根據 $trust$ 陣列，我們可以建立一個有向圖，其中 $trust[i] = [a_i, b_i]$ 表示 $a_i$ 信任 $b_i$ 。
• 對於每個人 $i$ ，我們可以計算他的 入度(indegree) 和 出度(outdegree) 。
• 根據題意，小鎮法官的入度為 $n-1$ ，出度為 $0$ ，因此我們只需要找到一個人，他的入度為 $n-1$ ，出度為 $0$ 即可。
• 時間複雜度：$O(n+m)$，其中 $n$ 為小鎮的人數，$m$ 為 $trust$ 陣列的長度。
• 空間複雜度：$O(n)$。

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indeg = [0] * (n + 1)
        outdeg = [0] * (n + 1)
        for a, b in trust:
            indeg[b] += 1
            outdeg[a] += 1
        for i in range(1, n + 1):
            if indeg[i] == n - 1 and outdeg[i] == 0:
                return i
        return -1

---

2024-02-23

🟡 2583. Kth Largest Sum in a Binary Tree 1374

題意

• 給定一顆二元樹的根節點 $root$ 和一個正整數 $k$ 。
• 樹中的 層和(level sum) 是指 同一層 上節點值的總和。
• 返回樹中第 $k$ 大的層和（不一定不同）。 如果樹少於 $k$ 層，則傳回 $-1$ 。

思路：BFS + Min Heap

• 使用 BFS 遍歷二元樹，並計算每一層的層和(level sum)。
• 要找到第 $k$ 大的層和，我們可以使用 Min Heap 來維護 當前最大的 $k$ 個層和。
• 時間複雜度：$O(n\log k)$，其中 $n$ 為二元樹的節點數。
• 空間複雜度：$O(k)$。

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        hp = [] # min heap, size k
        q = deque([root])
        while q:
            cur = 0
            for _ in range(len(q)):
                node = q.popleft()
                cur += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if len(hp) < k:
                heappush(hp, cur)
            else:
                if cur > hp[0]:
                    heapreplace(hp, cur) # first pop then push
        return hp[0] if len(hp) == k else -1

---

🟡 787. Cheapest Flights Within K Stops 1786

之所以咕了幾天才更新，除了在準備TOEIC外，也有部分原因是這題有許多不同的解法，需要花比較多時間整理。

題意

• 有 $n$ 個城市透過一些航班連接，給定一個陣列 $flights$ ，其中 $flights[i] = [from_i, to_i, price_i]$ ，表示該航班都從城市 $from_i$ 開始，以價格 $price_i$ 抵達 $to_i$。
• 給定所有的城市和航班，以及出發城市 $src$ 和目的地 $dst$，找到出一條最多經過 $k$ 站中轉的路線，使得從 $src$ 到 $dst$ 的 價格最低 ，並返回該價格。 如果不存在這樣的路線，則返回 $-1$ 。

思路

經過 $k$ 個中轉站，為從 $src$ 開始 走 $k+1$ 步 (包含終點)

方法一：BFS + Pruning

• 由於要在 $k+1$ 步內找到最低價格，我們可以使用 BFS 來進行搜尋。
• 將 $(u, d, s)$ 加入 BFS Queue 中，其中 $u$ 是當前城市，$d$ 是從 $src$ 到 $u$ 的距離，$s$ 是經過的中轉站數。
• 接著從 BFS Queue 中取出 $(u, d, s)$ ，並對所有的鄰居 $v$ 進行 鬆弛(relaxation) 操作。
  • 需要注意的是，在進行鬆弛時，不能使用在同一次迭代中更新的距離 ，因此在添加進 BFS Queue 時需要包含原本的距離。這點和Bellman-Ford的鬆弛操作類似，可以參考 @宫水三叶 的題解。
• 若以BFS遍歷完所有圖，則很有可能會超時，因此我們可以進行 剪枝(Pruning) ，當 $s > k$ 時，則不再進行BFS。
• 時間複雜度：$O(k \cdot n^2)$，其中 $n$ 為城市數，最多遍歷 $k$ 層，每層最多有 $n-1$ 個元素，每個元素最多有 $n-1$ 個相鄰節點。
• 空間複雜度：$O(n)$。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        g = [[float("inf")] * n for _ in range(n)] # Build graph
        adj = defaultdict(list)
        for u, v, w in flights:
            g[u][v] = min(g[u][v], w)
            adj[u].append(v)

        dist = [float('inf')] * n # Initialize distance
        dist[src] = 0

        q = deque([(src, 0, 0)]) # BFS
        while q:
            u, d, s = q.popleft()
            if s > k: # Pruning
                break
            for v in adj[u]:
                if dist[v] > d + g[u][v]:
                    dist[v] = d + g[u][v]
                    q.append((v, dist[v], s+1))
        return dist[dst] if dist[dst] != float('inf') else -1

方法二：Dynamic Programming(DP)

• 令 $dp[i][k]$ 表示在 $k$ 步內，從 $src$ 到 $i$ 的最小花費。
• 則對於每一條航班 $(u, v, w)$ ，我們可以進行 鬆弛(relaxation) 操作，即 $dp[v][k] = \min(dp[v][k], dp[u][k-1] + w)$ ，最後返回 $dp[dst][k]$ 即為答案。
• 可以看到 $dp[i][k]$ 只和 $dp[i][k-1]$ 有關，所以可以優化成一維陣列，這裡不做演示。
• 時間複雜度：$O((n+m) \cdot k)$，其中 $n$ 為城市數，$m$ 為航班數。總共有 $n \cdot k$ 個狀態，且進行 $k$ 次鬆弛，每次鬆弛需要考慮 $m$ 條航班，
• 空間複雜度：$O(n \cdot k)$ 或 $O(n)$。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dp = [[float("inf")] * (k + 2) for _ in range(n)] # k+2 是因為 k+1 步 (包含終點)
        dp[src][0] = 0

        for t in range(1, k + 2):
            for u, v, w in flights:
                dp[v][t] = min(dp[v][t], dp[u][t-1] + w)
        ans = min(dp[dst][t] for t in range(1, k + 2))
        return -1 if ans == float("inf") else ans

方法三：Bellman-Ford Algorithm

• Bellman-Ford 演算法是一種 單源最短路算法 ，可以處理有負權邊的圖。
• 每次迭代，我們都對所有的航班進行 鬆弛(relaxation) 操作，即 $dist[v] = \min(dist[v], dist[u] + w)$ ，經過 $k+1$ 次迭代後，可得到從 $src$ 到 $v$ 經過 $k+1$ 步 (即 $k$ 次中轉)的最小花費，最後返回 $dist[dst]$ 即為答案。
• 需要注意的是，在進行鬆弛時，不能使用在同一次迭代中更新的距離 ，因此在每次迭代時需要先複製一份原本的距離 $clone$ ，然後再進行鬆弛操作。
• 時間複雜度：$O((n+m) \cdot k)$，其中 $n$ 為城市數，$m$ 為航班數。總共進行 $k+1$ 次迭代，每次迭代需要 $O(n)$ 的時間備份距離，且每次迭代需要考慮 $m$ 條航班。
• 空間複雜度：$O(n^2)$。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        g = [[float("inf")] * n for _ in range(n)]
        for u, v, w in flights:
            g[u][v] = min(g[u][v], w)

        dist = [float('inf')] * n
        dist[src] = 0

        while k >= 0: # k+1 iterations
            clone = dist[:]
            for i in range(n):
                for j in range(n):
                    if clone[i] + g[i][j] < dist[j]:
                        dist[j] = clone[i] + g[i][j]
            k -= 1
        return -1 if dist[dst] == float("inf") else dist[dst]

方法四：Bellman-Ford Algorithm without building graph

• 由於 Bellman-Ford 的核心是進行 $k+1$ 次迭代，每次迭代都對所有的航班進行 鬆弛(relaxation) 操作，因此我們可以不需要建立圖，直接使用 $flights$ 進行鬆弛。
• 時間複雜度：$O((n+m) \cdot k)$，其中 $n$ 為城市數，$m$ 為航班數。總共進行 $k+1$ 次迭代，每次迭代需要 $O(n)$ 的時間備份距離，且每次迭代需要考慮 $m$ 條航班。
• 空間複雜度：$O(n)$。

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dist = [float('inf')] * n
        dist[src] = 0

        while k >= 0:
            clone = dist[:]
            for u, v, w in flights:
                if clone[u] + w < dist[v]:
                    dist[v] = clone[u] + w
            k -= 1
        return -1 if dist[dst] == float("inf") else dist[dst]

參考資料

• 【宫水三叶】运用 Bellman Ford 求解有限制的最短路问题
• 【彤哥来刷题啦】一题六解：1ms & 100% & 记忆化搜索 & DP & DP优化 & BFS & Bellman-Ford & SPFA！

---

2024-02-24

🟡 2476. Closest Nodes Queries in a Binary Search Tree 1597

題意

• 給定一個 Binary Search Tree(BST) 的根節點 $root$ ，以及一個長度為 $n$ 的正整數陣列 $queries$ 。
• 返回一個長度為 $n$ 的二維陣列 $answer$ ，其中 $answer[i] = [min_i, max_i]$
  • $min_i$ 是樹中 小於等於 $queries[i]$ 的 最大值 。 如果不存在這樣的值，則使用 $-1$ 來代替。
  • $max_i$ 是樹中 大於等於 $queries[i]$ 的 最小值 。 如果不存在這樣的值，則使用 $-1$ 來代替。

思路：Inorder Traversal + Binary Search

• 根據題意，對於每個 $queries[i]$ ，需要找到在BST中，最接近 $queries[i]$ 的節點，並返回這兩個節點的值。
• 為了找出這兩個節點，需要將節點按照其值進行排序。由於是 Binary Search Tree(BST) ，因此其 Inorder Traversal 即為排序後的節點列表。
  • 若 $q$ 在BST中，則顯然地，所求即為 $[q, q]$ 。
  • 若 $q$ 不在BST中，則$min_i < q$ 且 $max_i > q$ ，所求為 $q$ 之前後節點。
• 因此可以用 Binary Search 找到 $q$ 的前後節點的值。令 $idx1$ 為第一個不小於 $q$ 的元素的索引， $idx2$ 為第一個大於 $q$ 的元素的索引。
  • 若 $idx1$ 和 $idx2$ 相等，則 $q$ 不在BST中，若無超出索引範圍，則 $min_i$ 和 $max_i$ 分別為 $idx1-1$ 和 $idx1$ 的值。
  • 若 $idx1$ 和 $idx2$ 不相等，則代表 $q$ 在BST中，所求即為 $[q, q]$ 。
• 時間複雜度：$O(n \log n)$，其中 $n$ 為BST的節點數，每次查找 $q$ 的前後節點的值需要 $O(\log n)$ 的時間。
• 空間複雜度：$O(n)$。

class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        nodes = []
        def inorder(node):
            if not node:
                return []
            inorder(node.left)
            nodes.append(node.val)
            inorder(node.right)
        inorder(root)

        ans = []
        for q in queries:
            idx1 = bisect_left(nodes, q) # Find the first element that is not less than q (>=)
            idx2 = bisect_right(nodes, q) # Find the first element that is greater than q (>)
            if idx1 != idx2: # q is in the tree
                ans.append([q, q])
            else:
                if idx1 == 0:
                    ans.append([-1, nodes[idx1]])
                elif idx1 == len(nodes):
                    ans.append([nodes[idx1-1], -1])
                else:
                    ans.append([nodes[idx1-1], nodes[idx1]])
        return ans

---

🔴 2092. Find All People With Secret 2004

題意

• 給定一個整數 $n$ ，表示有 $n$ 個專家，編號從 $0$ 到 $n-1$ 。另外給定一個下標從 $0$ 開始的二維整數陣列 $meetings$ ，其中 $meetings[i] = [x_i, y_i, time_i]$ 表示專家 $x_i$ 和專家 $y_i$ 在時間 $time_i$ 要開一場會。
• 專家 $0$ 知道一個 秘密 。最初，他在時間 $0$ 將這個秘密分享給了專家 $firstPerson$ 。 接著，這個秘密會在每次有知道這個秘密的專家參加會議時傳遞。在每次會議中，如果專家 $x_i$ 在時間 $time_i$ 時知道這個秘密，那麼他將會與專家 $y_i$ 分享這個秘密，反之亦然。
• 秘密傳遞是 瞬間發生 的，也就是說，在同一時間，一個專家不光可以接收到秘密，還能在其他會議上與其他專家分享。
• 在所有會議都結束之後，返回所有知曉這個秘密的專家清單，可以按照 任何順序 返回答案。

思路：Disjoint Set Union(DSU)

• 這題的關鍵在於如何模擬秘密的傳遞，知道秘密和不知道秘密的專家可以看作是不同集合(Set)，而進行會議則是對這兩個集合進行 聯集(Union) 操作，因此可以使用 Disjoint Set Union (DSU) 來模擬秘密的傳遞。
• 首先，我們可以依照專家的編號建立一個大小為 $n$ 的 Disjoint Set Union(DSU) ，並且將每個專家的父節點初始化為自己，即將每個專家視為一個集合。
• 依照題意，在初始化時，專家 $0$ 知道秘密，且告知了專家 $firstPerson$ ，因此我們可以將專家 $0$ 與 $firstPerson$ 進行 聯集(Union) 操作。且因為會議進行需按照時間先後順序，我們可以將會議按照時間進行排序。
• 由於秘密是 瞬間發生 的，我們可以先假設同一時間下的所有會議均能傳遞秘密，也就是對其進行 聯集(Union) 操作。然而，在每個 連通分量(connected component) 中，需要有人知道秘密才能傳遞。因此，在進入下一個時間點時，需要對前一個時間點涉及的所有專家進行遍歷，確定其是否確實知道秘密，若不知道秘密，則將其 隔離(isolate) ，即將其父節點設為自己。
• 最後，遍歷所有專家，找出與專家 $0$ 屬於同一集合(Set)的專家，即為知道秘密的專家。
• 時間複雜度：$O(m \log m + m \alpha(n))$，其中 $m$ 為會議數，$n$ 為專家數，$\alpha(n)$ 為Ackermann函數的反函數 ，是一個極為緩慢增長的函數。排序會議需要 $O(m \log m)$ 的時間，並且進行 $m$ 次 聯集(Union) 操作，每次 聯集(Union) 操作的時間複雜度可以視為 $O(\alpha(n))$ 。
• 空間複雜度：$O(n)$。

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        pa = [i for i in range(n)] # parent

        def find(x: int) -> int:
            if pa[x] != x:
                pa[x] = find(pa[x])
            return pa[x]
        
        def union(x: int, y: int) -> None:
            pa[find(x)] = find(y)

        def isolate(x: int) -> None:
            pa[x] = x

        def isSame(x:int, y:int) -> bool:
            return find(x) == find(y)

        meetings.sort(key=lambda x: x[2]) # sort by time
        union(0, firstPerson) # firstPerson 知道秘密

        time = 0 # 同一時間的會議，在每個連通分量中，需要有人知道秘密才能傳遞
        people = set() # 這個時間點進行會議的人
        for x, y, t in meetings:
            if t != time: # 進入下一個時間點，檢查前一個時間點是否有人知道秘密
                time = t
                for p in people:
                    if not isSame(firstPerson, p):
                        isolate(p)
                people = set()
            union(x, y)
            people.add(x)
            people.add(y)

        ans = []
        for i in range(n):
            if isSame(i, firstPerson):
                ans.append(i)
        return ans

---

2024-02-25

🟡 235. Lowest Common Ancestor of a Binary Search Tree

題意

• 給定一個Binary Search Tree(BST)，以及兩個節點 $p$ 和 $q$ ，找到它們的 最近公共祖先(Lowest Common Ancestor, LCA)。
• 最近公共祖先(Lowest Common Ancestor, LCA) 定義為：「對於Binary Tree的兩個節點p、q，最近公共祖先表示為一個節點x，滿足x是p、q的祖先且x的深度盡可能大（一個節點也可以是它自己的祖先）」。

思路：遞迴(Recursion)

• 與 236. Lowest Common Ancestor of a Binary Tree (2024-02-09) 類似的討論方式，若 $root$ 是 $p$, $q$ 的 最近共同祖先(Lowest Common Ancestor, LCA)，則只可能為以下情況之一：
  1. $p$ 和 $q$ 分別在 $root$ 的 左子樹和右子樹中
  2. $p = root$，且 $q$ 在 $root$ 的 左子樹或右子樹中
  3. $q = root$，且 $p$ 在 $root$ 的 左子樹或右子樹中
• 由於這題是BST，所以可以由大小關係來簡化判斷
  • 若 p 和 q 皆小於 root，則最近共同祖先必在 root 的左子樹中，可遞迴至左子樹中求解，反之亦然。
  • 否則，則 $p$ 和 $q$ 分別在 $root$ 的 左/右子樹中，或是 $p$ 和 $q$ 其中一個是 $root$，則 $root$ 即為最近共同祖先。
• 時間複雜度：$O(h)$，其中 $h$ 為BST的高度。
• 空間複雜度：$O(h)$，遞迴使用的堆疊(Stack)空間。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val: # p 和 q 都在左子樹中
            return self.lowestCommonAncestor(root.left, p, q) 
        elif p.val > root.val and q.val > root.val: # p 和 q 都在右子樹中
            return self.lowestCommonAncestor(root.right, p, q)
        else: # p 和 q 分別在 root 的 左/右子樹中，或是p 和 q 其中一個是 root
            return root 

---

🔴 2709. Greatest Common Divisor Traversal 2172

題意

• 給定一個下標從 $0$ 開始的整數陣列 $nums$，你可以在一些下標之間遍歷。 對於兩個下標 $i$ 和 $j$（$i \neq j$），當且僅當 $\text{gcd}(nums[i], nums[j]) > 1$ 時，我們可以在兩個下標之間通行，其中 $\text{gcd}$ 是兩個數的 最大公因數(Greatest Common Divisor) 。
• 判斷 $nums$ 中 任意 兩個滿足 $i < j$ 的下標 $i$ 和 $j$ ，是否存在若干次通行可以從 $i$ 遍歷到 $j$ 。如果任意符合條件的下標對都可以遍歷，那麼返回 $\text{true}$，否則返回 $\text{false}$。

限制

• $1 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums[i]} \leq 10^5$

思路：質因數分解(Prime Factorization) + Disjoint Set Union(DSU)

• 由於題目要求的是 任意 兩個滿足 $i < j$ 的下標 $i$ 和 $j$ ，是否存在若干次通行可以從 $i$ 遍歷到 $j$ ，因此我們可以將所有的數字進行 質因數分解(Prime Factorization) ，並將具有相同質因數的數字連通，將所有連通分量中的數字視為同一個集合，即可使用 Disjoint Set Union(DSU) 來解決這個問題。
• 根據數據範圍，我們可以使用 埃氏篩(Sieve of Eratosthenes) 來預處理(Preprocessing) 範圍內所有數字的質因數(Prime)。
  • 其核心思想是由小到大遍歷所有數字，對於每個質數，將其所有的倍數標記為非質數，並將該質數作為其倍數的質因數，若遍歷到的數字仍未被標記，則其為質數。
• 在連通時，我們不直接將兩個數字進行相連 ，而是對於 $nums[i]$ 的所有質因數 $p$ ，將 $p$ 與 $nums[i]$ 進行 聯集(Union) 操作。因此在初始化DSU時，需要宣告 $n+mx+1$ 個節點，前 $n$ 個節點對應 $nums$ 中的數字，後 $mx+1$ 個節點對應 $0$ 到 $mx$ 的所有數字，儘管非質數的部分不會被使用到，但是為了方便計算，我們可以將其保留。
• 最後，遍歷 $0$ 到 $n-1$ 的所有數字，若對所有滿足 $i < j$ 的下標 $i$ 和 $j$，$nums[i]$ 和 $nums[j]$ 屬於同一個集合，則返回 $\text{true}$，否則返回 $\text{false}$。這裡檢查 $nums[i]$ 是否和 $nums[0]$ 屬於同一個集合即可。
• 時間複雜度：$O(n \log (\log n) + n \log n)$，其中 $n$ 為數字的個數，$mx$ 為數字的最大值。預處理所有數字的質因數需要 $O(n \log \log n)$ 的時間，初始化DSU需要 O(n + mx) 的時間，並對 $n$ 個數字的質因數進行聯集操作，此部分需要 $O(n \log n)$ 的時間 (存疑) 。
• 空間複雜度：$O(n + mx)$。

# Initialize the list of prime factors for each number
MAXN = 10 ** 5 + 5
fac = defaultdict(list)
for i in range(2, MAXN):
    if not fac[i]: # i is prime
        for j in range(i, MAXN, i): # mark all multiples of i
            fac[j].append(i)

class Solution:
    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        mx = max(nums)

        root = list(range(n + mx + 1))

        def find(x): # find root
            if root[x] != x:
                root[x] = find(root[x]) # path compression
            return root[x]

        def union(x, y):
            root[find(x)] = find(y)

        for i, num in enumerate(nums):
            for p in fac[num]:
                union(i, n + p) # connect node i to node n+p, all nodes connected to n+p have prime factor p 

        # check if all numbers in range(n) are connected
        r = find(0)
        for i in range(1, n):
            if find(i) != r:
                return False
        return True

---

2024-02-26

🟢 938. Range Sum of BST 1335

題意

• 給定二元搜尋樹(Binary Search Tree, BST)的根節點 $root$ ，以及兩個整數 $low$ 和 $high$ ，返回所有節點值位於範圍 $[low, high]$ 之間的節點值的總和。

思路：深度優先搜索(DFS) + 剪枝(Pruning)

• 由於是BST，因此可以利用BST的性質進行 剪枝(Pruning) ，即當當前節點的值小於 $low$ 時，則只遍歷右子樹；當當前節點的值大於 $high$ 時，則只遍歷左子樹。
• 進行DFS遍歷，對於每個節點，若其值在範圍 $[low, high]$ 之間，則將其值加入總和中。
• 時間複雜度：$O(n)$，其中 $n$ 為BST的節點數。
• 空間複雜度：$O(h)$，其中 $h$ 為BST的高度。

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        def dfs(root):
            if not root:
                return 0
            if root.val < low:
                return dfs(root.right)
            if root.val > high:
                return dfs(root.left)
            return root.val + dfs(root.left) + dfs(root.right)
        return dfs(root)

---

🟢 100. Same Tree

題意

• 給定兩個二元樹(Binary Tree)的根節點 $p$ 和 $q$ ，返回這兩棵樹是否相同。
• 如果兩個樹在結構上相同，並且節點具有相同的值，則認為它們是相同的。

思路：遞迴(Recursion)

• 若 $p$ 和 $q$ 皆非空節點，且其值相等，則進行遞迴判斷其左右子樹是否相同；若 $p$ 和 $q$ 皆為空節點，則返回 $\text{true}$；若 $p$ 和 $q$ 一個為空節點，另一個不為空節點，則返回 $\text{false}$。後兩者可以在確認 $p$ 和 $q$ 皆不為非空節點後，合併成 $p == q$。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(h)$，其中 $h$ 為樹的高度，即遞迴使用的堆疊(Stack)空間。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        return p == q

---

2024-02-27

🔴 2867. Count Valid Paths in a Tree 2428

前幾天的每日一題出了兩次DSU，今天看到這題就直覺用DSU寫了，但官方解答是用DFS寫的，在速度上快了一些。

題意

• 給定一棵由 $n$ 個節點組成的無向樹 ，節點編號為 $1$ 到 $n$ 。給定一個長度為 $n-1$ 的二維整數陣列 $edges$ ，其中 $edges[i] = [u_i, v_i]$ 表示節點 $u_i$ 和 $v_i$ 在樹中有一條邊。
• 返回樹中的 有效路徑數目 。
• 路徑 $(a, b)$ 被視為 有效 路徑，當且僅當從節點 $a$ 到節點 $b$ 的路徑中，存在且僅存在一個 質數。
• 注意：
  • 路徑 $(a, b)$ 是以節點 $a$ 為起點，以節點 $b$ 為終點的節點序列，序列中的節點互不相同，且序列中每兩個相鄰節點在樹中存在一條邊連接。
  • 路徑 $(a, b)$ 和路徑 $(b, a)$ 被視為 相同 的路徑，只會被計算 一次。

限制

• $1 \leq n \leq 10^5$
• $edges.length = n - 1$
• $edges[i].length = 2$
• $1 \leq u_i, v_i \leq n$

思路：質數判定 + 枚舉質數 + Disjoint Set Union(DSU) / Deep First Search(DFS) + 乘法原理

• 根據數據範圍，我們可以使用 埃氏篩(Sieve of Eratosthenes) 來預處理(Preprocessing) 範圍內所有數字的是否為質數($isPrime$)。
  • 其核心思想是由小到大遍歷所有數字，對於每個質數，將其所有的倍數標記為非質數，並將該質數作為其倍數的質因數，若遍歷到的數字仍未被標記，則其為質數。
  • 和 2709. Greatest Common Divisor Traversal (2024-02-25)中所使用的方法類似，但本題中我們只關注是否為質數，而非對所有數字進行質因數分解，因此我們只要考慮至 $\text{floor}(\sqrt{MAXN})$ 即可；且在標記質數時，可以直接從 $i*i$ 開始標記，因為 $i$ 的所有小於 $i$ 的倍數已經被標記過了。
• 需要注意的是，由於是無向樹，可以以任何點作為根節點 。
• 由於有效路徑上只能有一個質數，因此路徑的兩端點只會有兩種情況：兩端皆非質數 、或一端為質數一端為非質數 。因此可以枚舉質數 作為根節點，接著將非質數節點與非質數節點連通，考慮與該質數相鄰的所有非質數節點的連通分量(connected component) 大小，以乘法原理 計算有效路徑數目：
  • 從每個連通分量內部選擇一個節點作為起點，再從另外一個連通分量內部選擇一個節點作為終點，則有效路徑數目為：起點數量 * 終點數量。
  • 或是以質數節點作為起點，再從與質數節點相鄰的非質數節點中選擇一個節點作為終點，則有效路徑數目為：非質數節點數量。
• 需注意路徑 $(a, b)$ 和路徑 $(b, a)$ 被視為 相同 的路徑，只會被計算 一次。我們可以紀錄已經被考慮過的非質數節點數量 $cur$ ，並再考慮新的大小為 $size$ 的連通分量時，將 $cur$ 乘上 $size$ 後加入答案中，再把 $cur$ 加上 $size$。考慮完所有連通分量後，等同考慮完兩側皆為非質數節點的情況，而此時 $cur$ 即為所有非質數節點的數量，故再加上 $cur$ 本身，也就是以質數節點作為起點的有效路徑，即可得到所有經過該質數的有效路徑數量。
  • 舉例來說，假設我們枚舉了質數 $x$ 作為根節點，並且與 $x$ 相鄰的非質數節點的連通分量分別為 $2,3,4$，則有效路徑數目為 $(0) * 2 + (2) * 3 + (2+3) * 4 + (2+3+4)$。
• 至於連通分量(connected component) 的大小，可以使用Disjoint Set Union(DSU) 或深度優先搜索(DFS) 來計算，後者在速度上會快一些。

方法一：質數判定 + Disjoint Set Union(DSU) + 乘法原理

• 對於每個非質數節點 $x$，我們可以將其與與其相鄰的非質數節點 $y$ 進行 聯集(Union) 操作，操作時以 $x$ 的根節點 $fx$ 作為根節點，並將其連通分量的大小相加，即可求得連通分量的大小。
• 時間複雜度：$O(n \log (\log n) + n\alpha(n) )$，其中 $n$ 為節點數。預處理所有數字的質因數需要 $O(n \log \log n)$ 的時間，初始化DSU需要 O(n) 的時間，總共有 $n-1$ 條邊，需要聯集 $O(n)$ 次，每次聯集的時間複雜度可以視為 $O(\alpha(n))$ ，其中 $\alpha(n)$ 為Ackermann函數的反函數 ，是一個極為緩慢增長的函數。
• 空間複雜度：$O(n)$。

# Initialize the list of prime numbers for each number
MAXN = 10 ** 5 + 5
isPrime = [True] * MAXN
isPrime[0] = isPrime[1] = False
for i in range(2, math.isqrt(MAXN) + 1):
    if isPrime[i]: # i is prime
        for j in range(i*i, MAXN, i): # mark all multiples of i
            isPrime[j] = False

class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        # 用 Disjoint Set Union(DSU) 計算所有非質數節點的連通分量大小
        pa = list(range(n + 1)) # parent

        def find(x: int) -> int: # find root
            if pa[x] != x:
                pa[x] = find(pa[x])
            return pa[x]

        size = [1] * (n + 1) # size of connected component
        for x in range(1, n + 1):
            if isPrime[x]:
                continue
            fx = find(x)
            for y in g[x]:
                if isPrime[y]:
                    continue
                fy = find(y)
                if fy == fx:
                    continue
                size[fx] += size[fy] # 以 x 為根節點合併
                pa[fy] = fx
        ans = 0
        for x in range(1, n+1): # 枚舉所有質數節點 x
            if not isPrime[x]:
                continue
            cur = 0 # 起點數量
            for y in g[x]: # 枚舉與 x 相鄰的非質數節點 y
                if isPrime[y]:
                    continue
                fy = find(y)
                ans += cur * size[fy] # 乘法原理：起點數量 * 終點數量
                cur += size[fy]
            ans += cur # 以 x 為終點
        return ans

方法二：Deep First Search(DFS) + 乘法原理

• 用DFS找出相連的連通分量中有多少個非質數節點，並使用類似記憶化搜索的方式，將已經計算過的連通分量的大小記錄下來，以減少重複計算。
• 時間複雜度：$O(n \log (\log n) + n)$，其中 $n$ 為節點數。預處理所有數字的質因數需要 $O(n \log \log n)$ 的時間，DFS需要 $O(n)$ 的時間。
• 空間複雜度：$O(n)$。

# Initialize the list of prime numbers for each number
MAXN = 10 ** 5 + 5
isPrime = [True] * MAXN
isPrime[0] = isPrime[1] = False
for i in range(2, math.isqrt(MAXN) + 1):
    if isPrime[i]: # i is prime
        for j in range(i*i, MAXN, i): # mark all multiples of i
            isPrime[j] = False

class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        def dfs(x: int, pa: int) -> None:
            nodes.append(x)
            for y in g[x]:
                if y == pa or isPrime[y]:
                    continue
                dfs(y, x)

        ans = 0
        size = [0] * (n + 1) # size of connected component
        for x in range(1, n+1): # 枚舉所有質數節點 x
            if not isPrime[x]:
                continue
            cur = 0 # 起點數量
            for y in g[x]: # 枚舉與 x 相鄰的非質數節點 y
                if isPrime[y]:
                    continue
                if size[y] == 0: # y 所在的連通分量尚未被計算過
                    nodes = []
                    dfs(y, -1)
                    for z in nodes: # 將該連通分量的所有非質數節點的 size 設為該連通分量的大小
                        size[z] = len(nodes)
                ans += cur * size[y] # 乘法原理：起點數量 * 終點數量
                cur += size[y]
            ans += cur # 以 x 為終點
        return ans

參考資料

• 【图解】O(n) 线性做法（Python/Java/C++/Go）

---

🟢 543. Diameter of Binary Tree

題意

• 給定一棵二元樹(Binary Tree)的根節點 $root$，返回該樹的 直徑(Diameter) 。
• 二元樹的 直徑(Diameter) 定義為樹中任意兩個節點之間最長路徑的長度，這條路徑可能經過根節點，也可能不經過。
• 兩個節點之間路徑的長度指的是它們之間的邊的數量。

思路：DFS

• 使用深度優先搜索(DFS)遍歷每個節點 $root$ ，令返回值為其深度。對於每個節點，可遞迴計算其左右子樹的深度 $left$ 和 $right$，
  • 經過該根節點的直徑為左子樹的深度加上右子樹的深度，即 $left+right$，以此更新答案。
  • 返回值為左子樹的深度和右子樹的深度中的最大值加上 $1$，即 $\max(left, right) + 1$。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(h)$，其中 $h$ 為樹的高度，即遞迴使用的堆疊(Stack)空間。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(root: TreeNode) -> int:
            nonlocal ans
            if not root:return 0
            left = dfs(root.left)
            right = dfs(root.right)
            ans = max(ans, left+right)
            return max(left, right) + 1
        dfs(root)
        return ans

---

2024-02-28

🟡 2673. Make Costs of Paths Equal in a Binary Tree 1917

題意

• 給定一個整數 $n$ 表示一棵 完美二元樹(perfect binary tree) 中節點的數目，節點編號從 $1$ 到 $n$。樹的根節點是 $1$，樹中每個節點 $i$ 都有兩個子節點，左子節點的編號是節點 $2 \times i$，右子節點的編號是 $2 \times i + 1$。
• 樹中的每個節點還有一個 成本(cost) ，由給定的 $0$ 索引整數陣列 $cost$ 表示，其中 $cost[i]$ 是節點 $i + 1$ 的成本。
• 在每次操作中，可以將樹中 任意 節點的成本 增加 $1$，操作可以執行 任意次。
• 目的是使根節點 $root$ 到每個樹葉節點 $leaf$ 上路徑的成本總和相等。返回使從根節點到每個樹葉節點的路徑成本相等的 最小操作次數。

注意：

• perfect binary tree 是指除樹葉節點外，每個節點都恰好擁有 $2$ 個子節點，且其所有葉子節點距離根節點的距離相同。
• 路徑成本 是路徑上所有節點的成本之和。

註：full/compelete/perfect binary tree的差別，說明及圖例來源自參考資料。

• full binary tree ：除了樹葉以外，每個節點都有兩個child。
• complete binary tree ：各層節點全滿，除了最後一層，最後一層節點全部靠左。
• perfect binary tree ：各層節點全滿。同時也是 full binary tree 和 complete binary tree 。

思路：Greedy + DP

• 路徑成本不同會發生在左右子樹的路徑和不同的情況，因此我們可以將問題轉化為對於每個節點，計算其左右子樹的最大路徑和，並將左右子樹的路徑和相等的最小代價。
• 若左右子樹的路徑和不同，此時可基於貪心思路，將比較小的路徑和增加到比較大的路徑和，使其相等。
• 需注意節點編號從 ，因此在計算左右子樹的最大路徑和時，需要將節點編號減去 $1$，方能取出對應的成本。

方法一：Top-Down DP

• 由上而下思考，令 $dfs(i)$ 表示節點 $i$ 以下的最大路徑和，則 $dfs(i) = \max(dfs(2 \times i), dfs(2 \times i + 1)) + cost[i-1]$，其中 $i$ 為節點編號，$cost$ 為節點成本，而使其左右子樹的路徑和相等的最小代價即為 $|dfs(2 \times i) - dfs(2 \times i + 1)|$。
• 時間複雜度：$O(n)$，其中 $n$ 為節點數。
• 空間複雜度：$O(\log n)$，即遞迴使用的堆疊(Stack)空間，因為樹的高度為 $O(\log n)$。

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        ans = 0
        def dfs(i: int) -> int: # 表示節點 i 以下的最大路徑和
            nonlocal ans
            # if i > n: return 0
            if 2 * i > n: return cost[i - 1] # leaf node
            l = dfs(2 * i)
            r = dfs(2 * i + 1)
            ans += abs(l - r) # 讓左右子樹的路徑和相等的最小代價
            return max(l, r) + cost[i - 1] # 編號從 1 開始
        dfs(1)
        return ans

方法二：Bottom-Up DP

• 相同的思路，但由下往上思考，從最後一個非葉子節點開始，計算其左右子樹的最大路徑和，並將左右子樹的路徑和相等的最小代價累加至答案中。
• 由於是 perfect binary tree ，因此 $n = 2^h - 1$，且最後一層的節點(葉子節點)數數量為 $2^{h-1}$ 。故最後一個internal node的編號為 $n // 2 + 1$，下標為 $n // 2$。
  • 或是由下標會不會超出索引範圍思考，若編號 $i$ 的節點為 internal node，則 $i * 2 < n$，即 $i <= n // 2$。
• 時間複雜度：$O(n)$，其中 $n$ 為節點數。
• 空間複雜度：$O(1)$。

class Solution:
    def minIncrements(self, n: int, cost: List[int]) -> int:
        ans = 0
        for i in range(n // 2, 0, -1): # 從最後一個internal node開始, i * 2 < n -> i <= n // 2
            ans += abs(cost[i * 2 - 1] - cost[i * 2]) # 讓左右子樹的路徑和相等的最小代價
            cost[i - 1] += max(cost[i * 2 - 1], cost[i * 2]) # 累加路徑和
        return ans

參考資料

• Binary Tree - 演算法筆記

---

🟡 513. Find Bottom Left Tree Value

題意

• 給定一棵二元樹的根節點 $root$，返回 最後一層中最左邊 節點的值。
• 假設至少有一個節點。

思路：BFS(Level Order Traversal)

方法一：每次保存該層的所有節點

• 按照題義，使用BFS遍歷每一層的節點，並在遍歷的同時保存該層的所有節點，最後返回最後一層的第一個節點的值。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            cur = []
            for _ in range(len(q)):
                node = q.popleft()
                cur.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return cur[0]

方法二：由右至左層序遍歷

• 由於題目要求返回最後一層中最左邊節點的值，因此我們可以使用由右至左的層序遍歷(Level Order Traversal)，即每次先將右子節點加入佇列(queue)，再將左子節點加入佇列，最後返回最後一個節點的值即可。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(n)$，但不用另外保存每一層的所有節點。

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
        return node.val

---

2024-02-29

🔴 2581. Count Number of Possible Root Nodes 2228

一開始用記憶化搜索，雖然能AC，但發現執行時間很差，看了題解後才知道可以用換根DP，效率提升很多。

題意

• Alice有一棵 $n$ 個節點的樹，節點編號為 $0$ 到 $n - 1$。給定一個長度為 $n - 1$ 的二維整數陣列 $edges$，其中 $edges[i] = [a_i, b_i]$ 表示樹中節點 $a_i$ 和 $b_i$ 之間有一條邊。
• Alice想要Bob找到樹的根。她允許Bob對她的樹進行多次 猜測 。在一次猜測中，他進行以下操作：
  • 選擇兩個 不相等 的整數 $u$ 和 $v$，且樹中必須存在邊 $[u, v]$。
  • Bob猜測樹中 $u$ 是 $v$ 的 父節點 。
• Bob的猜測用二維整數陣列 $guesses$ 表示，其中 $guesses[j] = [u_j, v_j]$ 表示Bob猜 $u_j$ 是 $v_j$ 的父節點。
• Alice 只會告訴Bob這些猜測裡面 至少 有 $k$ 個猜測的結果為 $true$ 。
• 給定二維整數陣列 $edges$，Bob的所有猜測 $guesses$ 和整數 $k$，請你返回可能成為樹根的 節點數目 。如果沒有這樣的樹，則返回 $0$。

思路：DFS + 記憶化搜尋(Memoization) DP / 換根(Rerooting) DP

方法一：DFS + 記憶化搜尋(Memoization) DP

• 由於給定了樹中的所有邊，因此可以假設某個節點為根，並進行深度優先搜索(DFS)來計算以該節點為根時的猜對數量。
• 由於可能會有多次DFS，因此可以使用 記憶化搜尋(Memoization) 來避免重複計算。
• 時間複雜度：$O(n^2)$，其中 $n$ 為節點數。
• 空間複雜度：$O(n^2 + n)$，建圖需要 $O(n^2)$ 的空間，記憶化搜索需要 $O(n)$ 的空間。
  • 對於每個節點 $u$，以及相鄰的節點 $v, w$，需要紀錄 $u$ 為樹根，$u$ 的父節點為 $v$，$u$ 的父節點為 $w$，總共 $3$ 種狀態。

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
        n = len(edges) + 1
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        st = set([(u, v) for u, v in guesses])
        
        @cache
        def dfs(u: int, fa: int) -> int:
            res = 0
            for v in g[u]:
                if v == fa: continue
                if (u, v) in st:
                    res += 1 # 對於這條邊的父子關係，猜對了
                res += dfs(v, u) 
            return res

        ans = 0
        for i in range(n):
            ans += (dfs(i, -1) >= k)
        return ans

方法二：DFS + 換根(Rerooting) DP

• 由於給定了樹中的所有邊，因此可以假設某個節點為根，並進行深度優先搜索(DFS)來計算以該節點為根時的猜對數量。
• 但每次換根時，只會改變 $1$ 組邊的父子關係，因此可以使用換根(Rerooting) DP來計算答案。

  如果 $x$ 和 $y$ 相鄰，那麼從「以 $x$ 為根的樹」變成「以 $y$ 為根的樹」時，只有 $x$ 和 $y$ 的父子關係改變，其餘相鄰節點的父子關係沒有變化。所以只有 $[x,y]$ 和 $[y,x]$ 這兩個猜測的正確性變了，其餘猜測的正確性不變。 (來自參考資料)

• 因此可以先計算出以 $0$ 為根時的猜對數量後再進行一次DFS，這次DFS的目的是計算換根後的猜對數量，若 $y$ 是 $x$ 的子節點，則 $y$ 的猜對數量的變化為 $cnt - ((x, y) in st) + ((y, x) in st)$。
• 時間複雜度：$O(n)$，其中 $n$ 為節點數。
• 空間複雜度：$O(n^2 + n)$，建圖需要 $O(n^2)$ 的空間，換根DP需要 $O(n)$ 的空間。

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
        n = len(edges) + 1
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        st = set([(u, v) for u, v in guesses])
        
        # @cache # 若用換根DP，只會執行一次DFS，因此不需要memoization
        def dfs(u: int, fa: int) -> int:
            res = 0
            for v in g[u]:
                if v == fa: continue
                if (u, v) in st:
                    res += 1 # 對於這條邊的父子關係，猜對了
                res += dfs(v, u) 
            return res

        def reroot(x: int, fa: int, cnt: int) -> int: # 再執行一次DFS來做換根
            ans = (cnt >= k) # 此時 cnt 為以 x 為根時的猜對數量，若滿足條件則答案+1
            for y in g[x]:
                if y == fa: continue
                ans += reroot(y, x, cnt - ((x, y) in st) + ((y, x) in st)) # 改以 y 為根時，猜對數量的變化
            return ans
        cnt0 = dfs(0, -1) # 以 0 為根時的猜對數量
        return reroot(0, -1, cnt0)

類題：換根DP

• 🔴 834. Sum of Distances in Tree 2197
• 🟡 310. Minimum Height Trees
• 🔴 2581. Count Number of Possible Root Nodes 2228 (本題)
• 🔴 2858. Minimum Edge Reversals So Every Node Is Reachable 2295

題單來自：@灵茶山艾府

參考資料

• 换根 DP（Python/Java/C++/Go）

---

🟡 1609. Even Odd Tree 1438

題意

• 若一個二元樹(Binary Tree)滿足以下幾個條件，則可以稱為 奇偶二元樹(Even Odd Tree) ：
  1. 設二元樹的根節點所在層下標為 $0$，根的子節點所在層下標為 $1$，根的孫節點所在層下標為 $2$，依此類推。
  2. 對於每個下標為偶數的偶數層，該層上的所有節點都為 嚴格遞增 的 奇整數（從左到右）。
  3. 對於每個下標為奇數的奇數層，該層上的所有節點都為 嚴格遞減 的 偶整數（從左到右）。
• 給定一個二元樹的根節點 $root$，如果該二元樹是 奇偶二元樹 ，則返回 $true$；否則返回 $false$。

思路：BFS / DFS

方法一：BFS(Level Order Traversal)保存每一層的節點值

• 使用廣度優先搜索(BFS)遍歷每個節點，並使用一個陣列 $arr$ 來保存每一層的節點值，再依據該層的下標來判斷是否滿足奇偶性以及遞增或遞減的條件即可。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        def isIncreasing(arr: List[int]) -> bool:
            for i in range(1, len(arr)):
                if arr[i] <= arr[i - 1]: return False
            return True
        q = deque([root])
        level = 0
        while q:
            arr = []
            for _ in range(len(q)):
                node = q.popleft()
                arr.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            if level % 2 == 0: # even
                if any(x % 2 == 0 for x in arr): return False
                if not isIncreasing(arr): return False
            else: # odd
                if any(x % 2 == 1 for x in arr): return False
                if not isIncreasing(arr[::-1]): return False
            level += 1
        return True

方法二：BFS(Level Order Traversal)，不保存每一層的節點值

• 在方法一的基礎上優化，不保存每一層的節點值，而是直接在BFS遍歷的過程中判斷是否滿足奇偶性以及遞增或遞減的條件即可。
• 為滿足在遍歷的同時檢查是否滿足條件，可以使用一個變數 $prev$ 來保存上一個節點的值，在每層開始時根據 $level$ 將 $prev$ 初始化為 $-\text{INF}$ (偶數層遞增) 或 $+\text{INF}$ (奇數層遞減)，並在遍歷每個節點時檢查是否滿足條件。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        q = deque([root])
        level = 0
        while q:
            prev = float('inf') if level % 2 else float('-inf')
            for _ in range(len(q)):
                node = q.popleft()
                if node.val % 2 == level % 2 or (level % 2 == 0 and node.val <= prev) or (level % 2 == 1 and node.val >= prev):
                    return False
                prev = node.val
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            level += 1
        return True

方法三：DFS + Hash Table

• 根據和方法二同樣的思路，我們也可以使用深度優先搜索(DFS)遍歷每個節點，但由於不會在遍歷完該層所有節點後才進入下層，因此需要使用一個Hash Table $last$ 保存每層最後一個節點的值。
• 在訪問每個節點時，我們可以根據該節點的值和 $last$ 來判斷是否滿足條件。
• 時間複雜度：$O(n)$，其中 $n$ 為樹的節點數。
• 空間複雜度：$O(n)$。

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        last = dict() # 紀錄每一層的最後一個數字
        
        def dfs(node, level):
            prev = last.get(level, float('inf') if level % 2 else float('-inf') ) 
            if node.val % 2 == level % 2 or (level % 2 == 0 and node.val <= prev) or (level % 2 == 1 and node.val >= prev):
                return False
            last[level] = node.val
            if node.left and not dfs(node.left, level + 1):
                return False
            if node.right and not dfs(node.right, level + 1):
                return False
            return True
        
        return dfs(root, 0)

---