Shannon's Blog 🐟 技術 | 生活 | 旅行

1 題目描述 簡單來說，這題是要實作一個Binary Search Tree的iterator，這個iterator可以讓你用next()的方式來取得下一個最小的值。然後使用 hasNext() 來判斷是否還有下一個最小值。 注意：題目有要求，空間複雜度必須是O(h)，h是樹的高度。 2 解法 當你看到 next() 目的是在取得『最小值』時。因為BST的特性是，任意節點的左子樹不空，那左子樹上所有節點的值均小於他的根節點的值。因此我們可以使用 inorder traversal 的方式來解這題，因為 inorder traversal 是一種由小到大(左-中-右)的方式遍歷BST。詳細關於inorder得實作可以參考這篇LeetCode 課前預習 - 掌握 BFS 與 DFS 指南。 2.1 解法1: Inorder Traversal 這邊我們可以使用stack來幫助我們做inorder traversal，然後每次呼叫next()的時候，我們就可以取得最小的值，在 hasNext() 的時候，我們只要判斷stack是否為空就可以了。 1234567891011121314 ...

1 題目描述 提供給你 postorder 與 inorder 的數列，請你建立一個二元樹。首先 讓我們先了解 postorder 與 inorder 的定義。 Inorder Traversal -> LEFT -> ROOT -> RIGHT Postorder Traversal -> LEFT -> RIGHT -> ROOT 2 解法 這題跟 105 題很像，只是順序不同，這題是 postorder 與 inorder，105 題是 preorder 與 inorder。這題的解法也是利用遞迴的方式來建立二元樹。 你會發現，postorder 最後一筆會是 Root，前面會先遍歷left sub-tree整顆跑完，才會再遍歷right sub-tree。而 inorder 是先遍歷left sub-tree，再遍歷root，最後是right sub-tree。你會發現 preorder 跟 inorder 的優缺點如下： postorder: 好處：因為最後一個值是root，所以可以直接取得root的值 缺點：無法知道左右子樹的範圍 ...

1 題目描述 給定一個sum，判斷是否存在一條從根節點到葉子節點的路徑，使得路徑上所有節點的值的和等於sum。 2 解法 這題不難，我們只要在往下遍歷的時候，每次減去當前節點的值，然後判斷是否為0即可。這題可以用DFS的方式解。 如果Root是空的回傳False，否則剪掉當前的節點 1234if not root: return Falseelse: targetSum -= root.val 如果發現root.left且root.right都是None代表觸底，檢查targetSum是否為None 12if not root.left and not root.right: return targetSum == 0 只要root還不是最底層的leaf，就繼續往下，如果左右子樹其中一個有True就回傳True 1return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum) 完整的程式碼 123456789class Solution: def h ...

1 題目描述 2 解法 看到這題的時候，就想要用 DFS 來解，順序大概是 root -> left 走過的節點都把他串起來，然後再 root -> right。那什麼時候要相加呢？當走到葉子節點（走到底時）的時候，就把這條路徑的數字相加起來就可以了。因此也可以用Recursive來解。 大問題：把每條路徑的數字相加起來。 小問題：假設我們已經走到底了，已經把數字串起來 最小的問題：把已經串完的數字，跟tot做加總，最後返回tot。 首先需要有個可以把每個節點串起來的變數path 123456def dfs(node, path): path = path + str(node.val) # 把每個節點串起來 if node.left: dfs(node.left, path) # 左子樹走到底 if node.right: dfs(node.right, path) # 右子樹走到底 當走到leaf節點時，要做加總 123456789def dfs(node, path): path = p ...

1 題目描述 簡單來說就是要把一個二元樹轉換成一個只有右子樹的鏈表。變成linkedlist。並且題目特別要求，使用 in-place 的方式。 2 解法 2.1 DFS 一開始你會發現基本上他就是DFS，依序走訪每個節點，然後把每個節點的左子樹接到右子樹，然後把左子樹設為空。 題目中，要求說是in-place，也就是說in-place 的意思可能更多說的是直接在原來的節點上改變指向，空間複雜度並沒有要求。所以這題也可以用遞迴解一下，這時候會讓我們想到DFS preorder的做法。詳細可以參考這篇LeetCode 課前預習 - 掌握 BFS 與 DFS 指南。 但是你在推導的時候會發現： 1234567 1 / \ 2 5 / \ \3 4 6preorder: 1 -> 2 -> 3 -> 4 -> 5 -> 6 我們知道題目給定的遍歷順序其實就是preorder遍歷的順序，所以我們能不能利用preorder遍歷的程式碼，每遍歷一個節點，就將上一個節點的右邊指標更新為目前節點。 preorder遍歷的順序是1 2 3 ...

1 題目描述 給定一個二元樹，然後每個節點有一個 next 指針，將它指向它右邊的節點。如果沒有右邊的節點，則設為 None。 題目有特殊要求，不能使用額外的空間，也就是說不能使用 Queue 來解這題。 2 解法 我們先走簡單路線，你會發現基本上就是把同一層的節點串起來，然後再串下一層的節點。因此我們可以使用BFS的方式來解這題。講到BFS的演算法，可以參考這篇LeetCode 課前預習 - 掌握 BFS 與 DFS 指南。 2.1 Queue 我們可以知道在Iterative的方式下，先不考慮題目限制，我們可以使用Queue來解這題。 BFS的演算法 123456789101112131415161718192021def bfs_traversal(root): def bfs(nodes): # 如果沒有節點，就直接返回 if not nodes: return next_level = [] # 裝下一層的每個節點 result = [] # 裝目前這層的節點值 ...

BFS vs DFS 二元樹走訪或稱二元樹遍歷，簡單來說就是走訪樹中各節點，轉化為線性關係。 主要分成兩種策略方式 深度優先搜尋（Depth-first Search，DFS）:從根節點出發，選擇某一子樹並以垂直方向由上到下處理，將其子節點訪問完後，再選擇另一子樹走訪。 廣度優先搜尋（Breadth-first Search，BFS）:從根節點出發，以水平方向由左到右走訪，將同階層的兄弟節點訪問完之後，再走訪下一階層的節點。 深度優先搜尋 DFS 假設根結點為N、左子樹為L、右子樹為R 前序走訪(Pre-order Traversal): NLR, 根節點 → 左子樹 → 右子樹 中序走訪(In-order Traversal): LNR, 左子樹 → 根節點 → 右子樹 後序走訪(Post-order Traversal): LRN, 左子樹 → 右子樹 → 根節點 簡單來說 都是先左子樹，再右子樹 preorder: root 在前面 inorder: root 在中間（裡面） postorder: root 在後面 preorder的實作 前序走訪： 順序是根節點 ...

1 題目描述 要把左右子樹對調，outside替換，inside也是替換。 2 解法 大問題：要把一個樹的左右子樹對調 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹對調。 最小的問題：當 root 是 None 時，回傳 None。 假設就是我們呼叫 invertTree(root.left) 與 invertTree(root.right) 會回傳對調後的左右子樹，我們只要把左右子樹對調就可以了。 1234567class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return None root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root 3 總結 大概花了20分，這題不難，但是我 ...

1 題目描述 檢查兩棵樹是否相同 2 解法 這題跟101-Symmetric Tree的解法很像，所以很簡單： 一樣套用 Recursion 的思維，我們先將大問題變成小問題 大問題：知道兩個樹是否相同 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹是對稱的。 大小關係式：(p.val == q.val) and (p.left, q.left) and (p.right, q.left) 當前的值相同 and 左子樹相同 and 右子樹相同 最小的問題：當 p 和 q 都觸底的時候，是如果都是None就代表True，但是當其中一邊有值，另一邊沒有值，就不相同了。 1234def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if not p or not q: return False return p.val == q.val and self.isSameTre ...

1 題目描述 提供給你 preorder 與 inorder 的數列，請你建立一個二元樹。首先 讓我們先了解 preorder 與 inorder 的定義。 Inorder Traversal -> LEFT -> ROOT ->RIGHT PreOrder Traversal -> ROOT -> LEFT -> RIGHT 2 解法 你會發現，preorder 第一筆會是 Root，後面會先遍歷left sub-tree整顆跑完，才會再遍歷right sub-tree。而 inorder 是先遍歷left sub-tree，再遍歷root，最後是right sub-tree。你會發現 preorder 跟 inorder 的優缺點如下： preorder: 好處：因為第一個值是root，所以可以直接取得root的值 缺點：無法知道左右子樹的範圍 inorder: 好處：可以知道左右子樹的範圍 缺點：無法知道root的值 因此我們要利用彼此雙方的好處，互補彼此的缺點。這時候我們就可以利用遞迴的方式來建立二元樹。 2.1 取su ...