LeetCode #70 Climbing Stairs - 刷題之旅
1 題目描述
爬樓梯,每次可以爬一階或是兩階,求爬到第n階有幾種方法。
2 解法
按照之前的介紹LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南,我很推薦把每一種步驟都嘗試寫出來看看,分別是:
Step1: Recursive
Step2: Recursive with Memoization
Step3: Iterative + Tabulation
Step4: Iterative with Constant Space
Step1: Recursive
最基本也是最蠢的就是我們要先發現,基本上走樓梯的方法數量是f(n) = f(n-1) + f(n-2),這樣的遞迴式,我們可以直接寫出來。
123456def climbStairs(n): if n == 1: return 1 if n == 2: return 2 return climbStairs(n-1) + climbStairs(n-2)
Step2: Recursive with Memoization
那我們就思考,是不 ...
LeetCode 課前預習 - 掌握 Dynamic Programming 的思維指南
前言
我希望可以熟悉DP的思維,剛好看到這篇Medium | Ultimate Guide to Dynamic Programming獲得蠻多的讚,所以打算這篇為基礎做筆記。
在解決Dynamic Programming重要的前提是:
耐心: DP問題通常需要花時間來思考,不要急著寫程式
熟悉遞迴: DP問題通常可以用遞迴的方式來解決,因此熟悉遞迴是很重要的
Recursion遞迴跟DP的不同
遞歸和動態規劃的主要關聯在於:
重疊子問題:如果一個遞歸算法在計算過程中重複解決相同的子問題,可以使用動態規劃來優化。這時,遞歸算法可以轉化為帶備忘錄的遞歸(自頂向下的動態規劃)。
最優子結構:如果一個問題的最優解可以由其子問題的最優解構成,那麼可以使用動態規劃來解決這個問題。
有一個很簡單的例子,使用Fibonacci數列來說明這兩個概念。
Fibonacci數列的遞歸解法123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) ...
LeetCode #98 Validate Binary Search Tree - 刷題之旅
1 題目描述
2 解法
我的問題是在,我一開始以為,只要把上一個節點,傳下去,跟下一層的節點進行比較就好了。但是我錯了!
我一開始腦子想著
你會發現上圖根本不是正確的二元搜尋樹,因為節點3比root小,不應該出現在右子樹中…所以我就卡住了。
2.2 使用Recursion
其實這題真的目的在於,在 左子樹,只要一往右走,就要考慮到根節點的值,不能大於root.val。而在右子樹,只要一往右走,就要考慮到根節點的值,不能小於root.val。我想了好久,都沒想到到底要怎麼樣知道走不同子樹的路線時(在左子樹還是在右子樹),還能知道當前到底走在哪個方向(一往右走,還是一往左走)…直到我試著畫出每個節點的上下限。
你會發現,根本不需要顧慮左還是右子樹,你會發現:
只要是往左走,max一定會更新成parent.val,而min則是繼承自上一層的min。
只要是往右走,min一定會更新成parent.val,而max則是繼承自上一層的max。
然後神奇的事情發生了:
因為在左子樹往右走時,max會一路繼承上一層的max,追溯到源頭就是root! 也就是說,我們在左子樹往右走時,m ...
LeetCode #230 Kth Smallest Element in a BST - 刷題之旅
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) # ...
LeetCode #103 Binary Tree Zigzag Level Order Traversal - 刷題之旅
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 ...
LeetCode #199 Binary Tree Right Side View - 刷題之旅
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 ...
LeetCode #236 Lowest Common Ancestor of a Binary Tree - 刷題之旅
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, ...
LeetCode #102 Binary Tree Level Order Traversal - 刷題之旅
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( ...
LeetCode #173 Binary Search Tree Iterator - 刷題之旅
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 ...
LeetCode #106 Construct Binary Tree from Postorder and Inorder Traversal - 刷題之旅
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的值
缺點:無法知道左右子樹的範圍 ...