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

1 題目描述 在二元搜尋樹中，找到第 k 小的節點值。 2 解法 看到二元搜尋樹就要知道，中序遍歷的結果就是一個排序好的陣列。因此我們可以透過中序遍歷的方式，來找到第 k 小的節點值。也就是先 left - root - right 的方式遍歷，當我們遍歷到第 k 個節點時，就可以回傳。大概可以這樣思考： 我們先走到底，也就是一直往左走，直到走到最左邊的節點。 當觸底的時候，我們開始計數，每次遍歷到一個節點，就把 count+1。 當 count 與 k 相等時，就回傳當前節點的值。 否則，遍歷右邊的節點。 那我們開始來一步步拆解這個問題吧！ Step 1 我們先走到底 123456def inorder(root): # 如果沒有節點了，就停止 if not root: return # 先走到底 inorder(root.left) Step 2 當觸底的時候，我們開始計數 1234567def inorder(root): if not root: return inorder(root.left) # ...

1 題目描述 給定一個二元樹，返回其節點值的之字形層序遍歷。換句話說，從左到右，逐層遍歷所有節點，然後每一層的節點值交替方向。 第 1 層從左到右，第 2 層從右到左，第 3 層從左到右，第 4 層從右到左，交替進行。 2 解法 2.1 我的解法 仔細看會發現一個規律，就是當我們在做層序遍歷的時候，我們可以透過BFS的方式，在不同的層，當發現是偶數層時，要從左到右，我們可以stack先塞right再left。而在奇數層時，要從右到左，我們可以stack先塞left再right。 123456789101112# 透過pop的方式取出最晚進去的節點node = nodes.pop()# 紀錄當前的層cur_level.append(node.val)# 如果是偶數層 Left到Right，因此我們先塞Right再Left，按照後進先出的方式達到 Left -> Right if level % 2 == 1: if node.right: next_level.append(node.right) if node.left: next_level.append(n ...

1 題目描述 假如你站在樹的右邊，看著樹，你會看到樹的右邊的節點。紀錄下來這些節點。 2 解法 一開始我看到這題的時候，腦子浮現的是，我就是努力的往右邊走，如果右邊沒辦法走了，就往左邊走，這樣就可以記錄下來右邊的節點了。但是我的想法無法解決以下這個情境： 12345 1 / \2 3 \ 5 以下的程式碼是錯誤的，他只會記錄到right subtree的最右邊，但是left subtree也就是 2 跟 5 節點不會被尋訪。 1234567891011121314class Solution: res = [] def rightSideView(self, root: TreeNode) -> List[int]: if root is None: return [] if root: self.res.append(root.val) # 如果右邊有節點，就往右邊走 if root.right: self.rightSideVie ...

1 題目描述 給一個二元樹，找到兩個節點的最低共同祖先。（祖先可以是自己） 2 解法 2.1 我的解法 看到這題的時候我腦子裡面出現兩種情況： 如果兩個節點在同一個子樹下（p是q的子節點或是q是p的子節點），那祖先會是p或是q。 如果兩個節點在不同的子樹下（p和q分別在左右子樹下），那祖先會是把他們倆分開時的root。 情境1: p 是 q 的祖先 或是 q 是 p 的祖先 情境2: p 和 q 在不同的子樹下 因此我們可以針對這兩種情況來寫遞歸。 情境1 我們可以建立一個function檢查兩個點是否在同一個子樹下，如果是的話，回傳p或是q。 123456def check_same_subtree(parent, child): if parent is None: return False if parent == child: return True return check_same_subtree(parent.left, child) or check_same_subtree(parent.right, ...

1 題目描述 給定一個二元樹，返回其節點值的層序遍歷。換句話說，從左到右，逐層遍歷所有節點。 2 解法 這題很明顯，我們可以使用BFS的方式來解，因為BFS是一種逐層遍歷的方式。 我們會需要 next_level 來存放下一層的節點，然後透過呼叫自己，放入next_level的節點。 nodes 是當層的所有節點。 values 是用來存放當層的節點值。 result 就是結果。 Recursive 12345678910111213141516171819class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: def bfs_helper(nodes): if not nodes: return next_level, values = [], [] for node in nodes: values.append( ...

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 ...