96. Unique Binary Search Trees - Medium 前往題目 想法 找規律? 思路 DP 0和1個節點是base case 嘗試把每個點當作root,左樹和右樹再各自當成root直到base case就可以推導出當前n總共有幾種樹 例如n=2總共是兩種可能的樹[0,1], [1,0],n=3是五種,因為[0,2], [1,1], [2, 0] => 2 + 1 + 2 = 5,n=4是14種,因為[0,3], [1,2], [2,1], 2024-11-16 Leetcode > Medium #Leetcode #心得 #Binary Search Tree #Binary Tree #Math #Dynamic Programming #Tree
1376. Time Needed to Inform All Employees - Medium 前往題目 想法 DFS找最長路徑 思路 BFS 先建立manager -> employees的map 然後就是一般的BFS,每個employee都要加上其manager的時間,這樣才是通知到那位employee的完整時間 每次到新的僱員時更新結果 Code class Solution { public int numOfMinutes(int n, int he 2024-11-16 Leetcode > Medium #Leetcode #心得 #Depth-First Search #Breadth-First Search #Tree
662. Maximum Width of Binary Tree - Medium 前往題目 想法 BFS 思路紀錄index就可以完美解決 一般的BFS 每個點除了把自身加入到queue,還要加入節點的index,表示在這層當中的index 利用節點的index就可以在最後算出這層可以多長 循環每層到最後取最大值 Code class Solution { public int widthOfBinaryTree(TreeNode root) 2024-11-11 Leetcode > Medium #Leetcode #心得 #Binary Tree #Depth-First Search #Breadth-First Search #Tree
106. Construct Binary Tree from Inorder and Postorder Traversal - Medium 前往題目 想法 postorder最後面一定是root 思路用root去定位,就可以得知左右子樹 dfs inorder和postorder都使用雙指針 當左指針超過右指針時回傳null,代表沒有子節點 取得根節點的值,以及其在inorder中的index 然後就可以建立父節點以及其左右子節點並遞迴呼叫 postorder只是拿來找根節點的 Code網友解答 class Solution 2024-11-07 Leetcode > Medium #Leetcode #心得 #Binary Tree #Array #Hash Table #Tree #Divide and Conquer
958. Check Completeness of a Binary Tree - Medium 前往題目 想法 BFS檢查左邊node是否為null 思路 BFS 紀錄上一個node,只要當前node不為null上一個node為null,就是有空缺處,回傳false Code網友解答 class Solution { public boolean isCompleteTree(TreeNode root) { Queue<TreeNod 2024-11-07 Leetcode > Medium #Leetcode #心得 #Binary Tree #Breadth-First Search #Tree
652. Find Duplicate Subtrees - Medium 前往題目 想法 每個可能都比較,不過至少會需要$O(N^2)$ 思路以空間換取時間,把走過的每個路徑都記錄下來,相同路徑就是duplicate preorder,其餘迭代順序也可以 遇到null就回傳null,路徑用字串紀錄 遇到相同路徑(字串)就加入根節點到結果 Code class Solution { Map<String, Integer> map; 2024-11-06 Leetcode > Medium #Leetcode #心得 #Binary Tree #Hash Table #Depth-First Search #Tree
427. Construct Quad Tree - Medium 前往題目 想法 讀不懂題目:D 思路第一次看到這種題,其實目的就只是分成一堆正方形,每個正方形裡面數值都一樣,並建立樹 DFS,每次都先檢查當前正方形裡是否數值完全相同(一開始是整個大正方形) 是的話直接回傳node,不是的話切割當前正方形為四象限每個象限再各自檢查是否數值相同 最後形成node,並加入子節點們,形成樹 Code class Solution { pu 2024-11-05 Leetcode > Medium #Leetcode #心得 #Array #Matrix #Tree #Divide and Conquer
1443. Minimum Time to Collect All Apples in a Tree - Medium 前往題目 想法 建立一棵樹? 儲存每個node的鄰居? DFS? 思路這題的關鍵在於 儲存每個node的鄰居 走訪全部節點 儲存鄰居 DFS走訪所有節點 不要走回父節點,不然會無限迴圈 呼叫dfs往鄰居接著走訪 當當前的節點是蘋果或是子節點有蘋果就代表來回需要兩秒,所以加上結果 Code class Solution { List<List<Intege 2024-10-30 Leetcode > Medium #Leetcode #心得 #Hash Table #Depth-First Search #Breadth-First Search #Tree
783. Minimum Distance Between BST Nodes - Easy 前往題目 想法 左右子樹和父節點比較就好 思路這樣的想法問題是孫子可能跟爺爺更近,相較於兒子 inorder可以在BST從最小數節點迭代到最大數節點 Code class Solution { int min; TreeNode prev; public int minDiffInBST(TreeNode root) { min 2024-10-26 Leetcode > Easy #Leetcode #心得 #Binary Search Tree #Binary Tree #Depth-First Search #Breadth-First Search #Tree
450. Delete Node in a BST - Medium 前往題目 想法 找到目標後直接刪除,把parent直接接到他的子樹 思路但這樣的想法有點問題,因為沒有考慮到樹的右子樹必須要大於父節點 Recursion 遇到null直接回傳root,回傳null也行,反正都是同樣的值 接著就看當前節點是否是Key,大於的話就往左邊繼續搜尋,反之往右邊 如果找到同樣的值,只有左或者右一個子樹的時候直接捨棄當前節點,接上子樹就好 如果他同時有右子樹和左子樹, 2024-10-25 Leetcode > Medium #Leetcode #心得 #Binary Search Tree #Binary Tree #Tree