LeetCode 解題筆記：3612. Process String with Special Operations I

作者：王一哲
日期：2026年6月16日


LeetCode 題目連結：3612. Process String with Special Operations I

解題想法

中等難度，標準的字串操作題。只要按照題目的要求處理字串即可，假設目前的內容儲存於 result，操作有以下 3 種：

1. * 移除 result 最後一項
2. # 複製 result 的所有內容
3. % 將 result 反序

如果用 Python 解題，可以先將結果存到串列，最後再接成字串並回傳，也可以直接用字串儲存結果。在我以前解題的經驗中，用串列的速度比較快，但沒想到這題是直接用字串儲存結果速度比較快。如果用 C++ 解題就直接用字串儲存結果，因為 C++ 的字串可以用 pop_back() 移除最後一項，也可以用 reverse 直接反序，操作上很方便。

Python 程式碼

Runtime: 23 ms, beats 69.08%. Memory: 25.92 MB, beats 44.08%.

class Solution:
    def processStr(self, s: str) -> str:
        arr = []  # 用串列儲存結果比較好操作
        for c in s:
            if c.isalpha():  # 字母，直接加到 arr 最後面
                arr.append(c)
            elif c == '*':  # 移除 arr 最後一項
                if arr: arr.pop()
            elif c == '#':  # 複製 arr 全部的內容
                if arr: arr += arr
            elif c == '%':  # arr 倒序
                arr.reverse()
        return "".join(arr)  # 組成字串再回傳

Runtime: 0 ms, beats 100.00%. Memory: 23.24 MB, beats 82.24%.

class Solution:
    def processStr(self, s: str) -> str:
        t = ""  # 用字串儲存結果
        for c in s:
            if c.isalpha():  # 字母，直接加到 t 最後面
                t += c
            elif c == '*':  # 移除 t 最後一項
                if t: t = t[:-1]
            elif c == '#':  # 複製 t 全部的內容
                if t: t += t
            elif c == '%':  # t 倒序
                t = t[::-1]
        return t  # 回傳 t

LeetCode 解題筆記：2095. Delete the Middle Node of a Linked List

作者：王一哲
日期：2026年6月15日


LeetCode 題目連結：2095. Delete the Middle Node of a Linked List

解題想法

中等難度題目。建一個走訪用的虛擬節點 dummy 並指向 head，用 while 迴圈掃過鏈結串列一輪計算節點數量 n。接下來先排除 n = 1 的特例，直接回傳 None 或 nullptr。接下來處理一般狀況，要刪除的目標節點索引值為 $mid = \lfloor n/2 \rfloor$。如果用 Python 解題可以將 dummy 重新指向 head，如果用 C++ 解題則再建一個走訪用的虛擬節點 newDummy 並指向 head，用一個 for 迴圈將 dummy 或 newDummy 往下走 $mid - 1$ 次。如果此時 dummy.next.next != None 或 newDummy->next->next != nullptr，將 dummy.next 指向 dummy.next.next 或是將 newDummy->next->next 指向 newDummy->next；反之，將 dummy.next 指向 None 或是將 newDummy->next->next 指向 nullptr。最後回傳 head。由於這個寫法要掃過整個鏈結串列 1.5 次，速度偏慢。

討論區有一個厲害的寫法，建兩個走訪用的虛擬節點 fast 及 slow，fast 從 head.next.next 開始一次走兩格、slow 從 head 開始一次走一格，當 fast 走到底時，slow 正好走到要被刪除的節點前一格，只要將 slow.next 指向 slow.next.next 即可。

Python 程式碼

Runtime: 105 ms, beats 29.69%. Memory: 61.93 MB, beats 98.82%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 先掃過鏈結串列一次計算節點數量
        dummy = ListNode()
        dummy = head
        n = 0
        while dummy:
            n += 1
            dummy = dummy.next
        
        # 特例，只有一個節點，回傳 None
        if n == 1: return None
        
        # 一般狀況，要刪除索引值 mid 的節點
        mid = n // 2
        dummy = head
        # 向下走 mid - 1 次
        for _ in range(mid - 1):
            dummy = dummy.next
        # 如果有 dummy.next.next，將 dummy.next 設定成 dummy.next.next
        if dummy.next.next:
            dummy.next = dummy.next.next
        else:  # 反之，設定為 None
            dummy.next = None
        
        # 回傳 head
        return head

非原創的快速解法。Runtime: 92 ms, beats 53.17%. Memory: 62.32 MB, beats 49.97%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 特例，只有一個節點，回傳 None
        if not head.next: return None

        # fast 從 head.next.next 開始 一次走兩格，slow 從 head 開始一次走一格
        slow = head
        fast = head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # 將 slow.next 指向 slow.next.next
        slow.next = slow.next.next
        # 回傳 head
        return head

LeetCode 解題筆記：2130. Maximum Twin Sum of a Linked List

作者：王一哲
日期：2026年6月14日


LeetCode 題目連結：2130. Maximum Twin Sum of a Linked List

解題想法

寫起來像簡單題的中等難度題。先用建一個走訪鏈結串列用的虛擬節點 dummy 並指向 head，用 while 迴圈及 dummy 掃過鏈結串列，將節點的值存到串列 nums 之中。如果 nums 的長度為 n，用 for 迴圈讀取 nums 左、右兩端的值加總，更新最大的 twin-sum。本來以為這麼直接的寫法時間排名應該很差，沒想到排名還算不錯。

Python 程式碼

Runtime: 50 ms, beats 88.51%. Memory: 63.10 MB, beats 16.16%.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # 掃過鏈結串列一輸，記錄每個節點的值於串列 nums
        nums = []
        dummy = head
        while dummy:
            nums.append(dummy.val)
            dummy = dummy.next
        # 掃過 nums，取左、右兩端的值相加，更新最大的 twin sum
        imax = 0
        n = len(nums)
        for i in range(n//2):
            imax = max(imax, nums[i] + nums[n-i-1])
        return imax

LeetCode 解題筆記：3838. Weighted Word Mapping

作者：王一哲
日期：2026年6月13日


LeetCode 題目連結：3838. Weighted Word Mapping

解題想法

簡單題。先用一層 for 迴圈從串列 words 之中讀取單字 word，假設 word 對應的加總 tot = 0；再用一層 for 迴圈從 word 依序讀取字元 c，計算 c 與字母 'a' 的編號差值，將編號差值於測資 weights 之中對應的值加到 tot。最後計算 25 - tot % 26 對應的字母加到答案之中。由於 Python 的字串操作速度較慢，我是先將字母存到串列 arr 之中，最後再用 join 將 arr 的內容組成字串後回傳。
後來我又想到，如果先建好一個反序的字母對照表，最後從 tot 的值找出對應字母的速度應該會快一點，沒想到這個方法大約需要 9 ms，直接用算的只要 4 ms，有點意外。

Python 程式碼

Runtime: 4 ms, beats 91.63%. Memory: 19.34 MB, beats 33.64%.

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        arr = []
        for word in words:
            tot = 0
            for c in word:
                tot += weights[ord(c) - ord('a')]
            arr.append(chr(25 - tot % 26 + ord('a')))
        
        return "".join(arr)

Runtime: 9 ms, beats 56.74%. Memory: 19.36 MB, beats 33.64%.

class Solution:
    def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
        table = ('z', 'y', 'x', 'w', 'v',
                 'u', 't', 's', 'r', 'q',
                 'p', 'o', 'n', 'm', 'l',
                 'k', 'j', 'i', 'h', 'g',
                 'f', 'e', 'd', 'c', 'b', 'a')
        arr = []
        for word in words:
            tot = 0
            for c in word:
                tot += weights[ord(c) - ord('a')]
            arr.append(table[tot % 26])
        
        return "".join(arr)
        

LeetCode 解題筆記：3559. Number of Ways to Assign Edge Weights II

作者：王一哲
日期：2026年6月12日


LeetCode 題目連結：3559. Number of Ways to Assign Edge Weights II

解題想法

困難題。由於節點數量 $n$ 可能多達 $10^5$ 個，用暴力法找出任意兩個節點之間的距離一定會超時，需要利用倍增法 (binary lift) 找出要查詢的兩個節點的最近共同祖先 (lowest common ancestor, LCA)，主要分成以下的步驟：

• 用接鄰矩陣存圖
• 先開好需要用到的串列，例如儲存每個節點深度用的 $depth$，儲存節點 $i$ 的第 $2^j$ 代祖先的二維串列 $up$。
• 用廣度優先搜尋 (BFS) 初始化 depth 和第 1 代祖先 up[i][0]
• 建立倍增表 $up$，其中 $up[i][j]$ 代表節點 $i$ 的第 $2^j$ 代祖先，由於 $2^j = 2^{j-1} \times 2^{j-1}$，因此建表時 $up[i][j] = up[up[i][j-1]][j-1]$。
• 寫一個查詢最近共同祖先的自訂函式 get_lca，找出代入的節點 $u, v$ 的最近共同祖先。
• 假設要查詢的節點為 $u, v$，最短距離 $dist = depth[u] + depth[v] - 2 \times depth[lca]$，答案為 $(2^{dist - 1}) % 1000000007$。

雖然可以 AC 但速度不快，需要再改進。

Python 程式碼

Runtime: 1463 ms, beats 35.85%. Memory: 99.75 MB, beats 88.68%.

from collections import deque

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        # --- 用接鄰矩陣存圖 ---
        n = len(edges) + 1
        adj = [[] for _ in range(n+1)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        # --- 用倍增法找節點 i 的第 2**j 代祖先
        LOG = 20  # 2**17 > 10**5，取 20 一定夠用
        depth = [0] * (n+1)  # 節點的深度
        up = [[1] * LOG for _ in range(n+1)]  # 儲存節點 i 的第 2**j 代祖先
        
        # --- 用 BFS 初始化 depth 和第 1 代祖先 up[i][0]
        que = deque([1])
        visited = {1}
        depth[1] = 0
        
        while que:
            u = que.popleft()
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    depth[v] = depth[u] + 1
                    up[v][0] = u  # v 的父節點為 u
                    que.append(v)
        
        # --- 建立倍增表 (binary lift)
        # up[i][j] 為 i 的第 2**(j-1) 代祖先的第 2**(j-1) 代祖先
        for j in range(1, LOG):  # 控制代數的 j 要放外㽪
            for i in range(1, n+1):
                up[i][j] = up[up[i][j-1]][j-1]  # 因為 2**j = 2**(j-1) * 2**(j-1)
                
        # --- 查詢最近共同祖先 (lowest common ancestor, LCA)
        def get_lca(u, v):
            # 防呆，確保 u 是比較深的節點
            if depth[u] < depth[v]:
                u, v = v, u
            # 將 u 往上提，直到跟 v 位於同一深度
            diff = depth[u] - depth[v]
            for j in range(LOG):
                if (diff >> j) & 1:
                    u = up[u][j]
            
            # 如果 u 往上提之後等於 u，直接回傳 u
            if u == v: return u
                
            # u 和 v 一起往上提，直到找到 LCA 的子節點
            for j in range(LOG - 1, -1, -1):
                if up[u][j] != up[v][j]:
                    u = up[u][j]
                    v = up[v][j]
                    
            return up[u][0] # 回傳 u 的父節點
        
        # --- 處理所有查詢 ---
        MOD = 10**9 + 7
        ans = []
        for u, v in queries:
            lca = get_lca(u, v)
            # 計算兩點在樹上的距離，邊的數量
            dist = depth[u] + depth[v] - 2 * depth[lca]
            
            if dist == 0:
                ans.append(0)
            else:
                ans.append(pow(2, dist - 1, MOD))
                
        return ans

LeetCode 解題筆記：3558. Number of Ways to Assign Edge Weights I

作者：王一哲
日期：2026年6月11日


LeetCode 題目連結：3558. Number of Ways to Assign Edge Weights I

解題想法

中等難度題目。我先用接鄰矩陣 $adj$ 存樹，題目規定根節點編號為 $1$，父節點編號小於子節點編號，但是測資 $edges$ 之中的節點編號可能會是 $u > v$，如果遇到這個狀況要先交換 $u, v$ 之後再存入 $adj$之中。接下來寫一個自訂函式 $dfs$，從根節點 $1$ 開始往下走找最大深度 max_depth。最後答案為 2**(max_depth - 1) % 1000000007。由於答案很大而且需要取餘數，如果用 Python 解題可以直接用內建的 pow，但如果用 C++ 解題要自己寫快速冪。 證明答案的過程如下。假設有 $m$ 條邊，且 $m \geq 1$，選擇其中奇數條邊設定為 $1$ 可以符合題目的要求，因此組合數為 $$ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots \binom{m}{m} = 2^{m-1} $$ 可以透過二項式定理 (binomial theorem) 導出這個結果。根據二項式展開式 $$ (1 + x)^m = \binom{m}{0} + \binom{m}{1}x + \binom{m}{2}x^2 + \dots + \binom{m}{m}x^m $$ 為了求出奇數項的總和，先對上式代入 $x = 1$，計算從 $m$ 條邊中隨意選擇任意數量的所有可能組合數 $$ 2^m = \binom{m}{0} + \binom{m}{1} + \binom{m}{2} + \binom{m}{3} + \dots + \binom{m}{m} $$ 再代入 $x = -1$，選擇偶數條邊的項，選擇奇數條邊的項變成負號。 $$ 0 = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \binom{m}{3} + \dots + (-1)^m \binom{m}{m} $$ 第 1 式減去第 2 式，偶數項會被完全抵消，而奇數項會變成兩倍： $$ 2^m - 0 = 2 \times \left[ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots \right] $$ 最後，將等式兩邊同除以 2，即可得到選擇奇數條邊的組合數總和： $$ \binom{m}{1} + \binom{m}{3} + \binom{m}{5} + \dots = \frac{2^m}{2} = 2^{m-1} $$

Python 程式碼

Runtime: 267 ms, beats 84.95%. Memory: 104.95 MB, beats 38.71%.

class Solution:
    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
        n = len(edges) + 1  # n 個節點，n-1 條邊
        adj = [[] for _ in range(n+1)]  # 用接鄰矩陣存樹
        for u, v in edges:
            if u > v:
                u, v = v, u
            adj[u].append(v)

        # 用 dfs 找最大深度
        max_depth = 0

        def dfs(u, depth):
            nonlocal max_depth
            # 遞迴出口
            if not adj[u]:
                max_depth = max(max_depth, depth)
            # 繼續往下走
            for v in adj[u]:
                dfs(v, depth + 1)
        
        # 呼叫 dfs
        dfs(1, 0)  # 從根節點 1、深度 0 開始
        
        # 答案是 2**(max_depth - 1) % (10**9 + 7)
        return pow(2, max_depth - 1, 10**9 + 7)

LeetCode 解題筆記：3691. Maximum Total Subarray Value II

作者：王一哲
日期：2026年6月10日


LeetCode 題目連結：3691. Maximum Total Subarray Value II

解題想法

困難題，昨天的 3689. Maximum Total Subarray Value I 加強版，難度提升很多。首先要建立稀疏表 (Sparse Tables)，用 st_max[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最大值，用 st_min[i][j] 儲存起點 $i$、長度 $2^{j}$ 的區間最小值。再用最大優先佇列 (max priority queue) $pq$ 儲存起點 $L = 0$ 到 $L = n-1$、終點皆為 $n-1$ 各區間的 `max_val - min_val`，從 $pq$ 之中取出 $k$ 個值。假設取出的區間為 $[L, R]$，先將值 $val$ 加到答案 $ans$ 之中，重新計算區間 $[L, R-1]$ 對應的值 val，再將 {val, L, R-1} 加入 $pq$ 之中。

Python 程式碼

Runtime: 3165 ms, beats 70.73%. Memory: 52.34 MB, beats 53.66%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        import heapq

        n = len(nums)  # 長度
        # 特例，nums 是空的或是 k 等於 0，回傳 0
        if n == 0 or k == 0:
            return 0
        
        # 1. 預先計算 log2(0) ~ log2(n)
        log_table = [0] * (n+1)
        for i in range(2, n+1):
            log_table[i] = log_table[i//2] + 1
        log_max = log_table[n] + 1  # log2 的上限
        
        # 2. 初始化 Sparse Tables，table[i][j] 代表長度 2**j、起點 i 的區間極值
        st_max = [[0] * log_max for _ in range(n)]
        st_min = [[0] * log_max for _ in range(n)]
        for i in range(n):
            st_max[i][0] = nums[i]
            st_min[i][0] = nums[i]
        
        # 3. 建立 Sparse Tables
        for j in range(1, log_max):  # 1 ~ log2(n)
            step = 1 << (j - 1)  # 2**(j-1)
            for i in range(n - (1 << j) + 1):  # 起點 i
                st_max[i][j] = max(st_max[i][j-1], st_max[i + step][j-1])
                st_min[i][j] = min(st_min[i][j-1], st_min[i + step][j-1])
        
        # 4. 自訂區間查詢函式
        def query(L, R):
            length = R - L + 1
            j = log_table[length]
            max_val = max(st_max[L][j], st_max[R - (1 << j) + 1][j])
            min_val = min(st_min[L][j], st_min[R - (1 << j) + 1][j])
            return max_val - min_val
        
        # 5. 初始化最大優先佇列
        pq = []
        for L in range(n):  # 起點 L = 0 ~ L = n-1
            val = query(L, n-1)  # 取區間 [L, n-1] 極值
            heapq.heappush(pq, (-val, L, n-1))
        
        # 6. 取前 k 大的極值
        ans = 0
        for _ in range(k):
            neg_val, L, R = heapq.heappop(pq)
            ans += -neg_val
            # 更新 pq，同一個起點 L，新的終點 R-1
            if R > L:
                new_val = query(L, R-1)
                heapq.heappush(pq, (-new_val, L, R-1))
        # 7. 回傳答案
        return ans

LeetCode 解題筆記：3689. Maximum Total Subarray Value I

作者：王一哲
日期：2026年6月9日


LeetCode 題目連結：3689. Maximum Total Subarray Value I

解題想法

中等難度的題目。題目給定一個陣列 $nums$，要從 $nums$ 之中選取 $k$ 個區間 $nums[l]$ 到 $nums[r]$，取區間的最大值、最小值相減，使 $k$ 個區間取出的相減結果加總最大。由於選取的區間可以重複，實際上這題就是取 $nums$ 的最大值 $imax$、最小值 $imin$，回傳 $(imax - imin) \times k$。

Python 程式碼

使用 max 及 min 取極值，速度較慢。Runtime: 15 ms, beats 48.00%. Memory: 26.40 MB, beats 88.80%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = min(nums), max(nums)
        return (imax - imin) * k

不使用 max 及 min 取極值，速度較快。Runtime: 11 ms, beats 69.60%. Memory: 25.75 MB, beats 100.00%.

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        imin, imax = float('inf'), -float('inf')
        for num in nums:
            if num < imin:
                imin = num
            if num > imax:
                imax = num
        return (imax - imin) * k

LeetCode 解題筆記：2161. Partition Array According to Given Pivot

作者：王一哲
日期：2026年6月8日


LeetCode 題目連結：2161. Partition Array According to Given Pivot

解題想法

中等難度題目。題目給一個串列 $nums$ 及樞紐值 $pivot$，要將 $nums$ 的值重新排列，小於 $pivot$ 的值按照原來的順序放在 $pivot$ 的左側，大於 $pivot$ 的值按照原來的順序放在 $pivot$ 的右側，中間是 $pivot$。$pivot$ 一定等於 $nums$ 其中一個或多個數字。我的想法是開兩個串列，其中 $ans$ 用來儲存答案，$large$ 用來儲存大於 $pivot$ 的值在 $nums$ 之中的索引值，另外用一個變數 $cnt$ 記錄 $pivot$ 於 $nums$ 之中的數量。接下來用一個 for 迴圈掃過 $nums$ 取出數值 $num$，如果 $num$ 等於 $pivot$ 就將 $cnt$ 加 1；如果 $num$ 小於 $pivot$ 就將 $num$ 加到 $ans$ 最後面；如果 $num$ 大於 $pivot$ 就將索引值 $i$ 加到 large。將 $cnt$ 個 $pivot$ 接到 $ans$ 之後。最後用一個 for 迴圈，取出 $large$ 記錄的索引值 $i$，將 $nums[i]$ 加到 $ans$ 最後面。程式碼再微調一下應該會更快。

Python 程式碼

Runtime: 40 ms, beats 33.75%. Memory: 34.31 MB, beats 5.07%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        ans, large = [], []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans.append(num)  # num 加入 ans
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans 加上 cnt 個 pivot
        ans += [pivot] * cnt
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans.append(nums[i])
        # 回傳答案
        return ans

用索引值找到填入數值的位置，速度反而比較慢。Runtime: 58 ms, beats 18.36%. Memory: 34.23 MB, beats 5.83%.

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n, le = len(nums), 0  # 長度，從左側填數字的索引值
        ans, large = [0]*n, []  # 答案，大於 pivot 的索引值
        cnt = 0  # 等於 pivot 的數字數量
        for i, num in enumerate(nums):  # 依序讀取 nums 的索引值及數字
            if num == pivot:  # num 等於 pivot
                cnt += 1  # 數量加 1
            elif num < pivot:  # num 小於 pivot
                ans[le] = num  # num 填入 ans[le]
                le += 1  # 向右移 1 格
            else:  # nums 大於 pviot
                large.append(i)  # 記錄索引值 i
        
        # ans[le] ~ ans[le + cnt] 填入 pivot
        ans[le : le+cnt] = [pivot] * cnt
        le += cnt  # 向右移 cnt 格
        # 將 large 對應的數字接到 ans 後面
        for i in large:
            ans[le] = nums[i]
            le += 1
        # 回傳答案
        return ans

LeetCode 解題筆記：2196. Create Binary Tree From Descriptions

作者：王一哲
日期：2026年6月7日


LeetCode 題目連結：2196. Create Binary Tree From Descriptions

解題想法

中級難度的題目。要用鏈結串列建二元樹。我先將每個節點的父節點、左子樹、右子樹分別存入字典之中，另外用一個集合儲存所有的節點。再找根節點，也就是所有節點當中唯一一個沒有父節點的節點。最後再用 BFS 或遞迴建樹。以下的程式碼速度不快，還可以再改進。

Python 程式碼

用 list 儲存待走訪的節點。Runtime: 202 ms, beats 15.04%. Memory: 28.30 MB, beats 24.19%.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
        # 儲存所有的節點值，記錄每個節點的父節點、左子節點、右子節點
        parent = dict()
        left_child = dict()
        right_child = dict()
        all_nodes = set()
        for p, c, lr in descriptions:
            all_nodes.add(p)
            all_nodes.add(c)
            parent[c] = p
            if lr == 1:
                left_child[p] = c
            else:
                right_child[p] = c
        # 找出根節點的值
        root_val = -1
        for node in all_nodes:
            if node not in parent:
                root_val = node
                break
        # 用 list 建樹
        root = TreeNode(val=root_val)
        que = [root]
        head = 0
        while head < len(que):
            curr = que[head]
            head += 1
            if curr.val in left_child:
                curr.left = TreeNode(val = left_child[curr.val])
                que.append(curr.left)
            if curr.val in right_child:
                curr.right = TreeNode(val = right_child[curr.val])
                que.append(curr.right)
        return root