106. Construct Binary Tree from Inorder and Postorder Traversal - Medium

前往題目 想法 postorder最後面一定是root 思路用root去定位，就可以得知左右子樹 dfs inorder和postorder都使用雙指針 當左指針超過右指針時回傳null，代表沒有子節點 取得根節點的值，以及其在inorder中的index 然後就可以建立父節點以及其左右子節點並遞迴呼叫 postorder只是拿來找根節點的 Code網友解答 class Solution
Leetcode > Medium
#Leetcode #心得 #Binary Tree #Array #Hash Table #Tree #Divide and Conquer

652. Find Duplicate Subtrees - Medium

前往題目 想法 每個可能都比較，不過至少會需要$O(N^2)$ 思路以空間換取時間，把走過的每個路徑都記錄下來，相同路徑就是duplicate preorder，其餘迭代順序也可以 遇到null就回傳null，路徑用字串紀錄 遇到相同路徑（字串）就加入根節點到結果 Code class Solution { Map<String, Integer> map;
Leetcode > Medium
#Leetcode #心得 #Binary Tree #Hash Table #Depth-First Search #Tree

427. Construct Quad Tree - Medium

前往題目 想法 讀不懂題目:D 思路第一次看到這種題，其實目的就只是分成一堆正方形，每個正方形裡面數值都一樣，並建立樹 DFS，每次都先檢查當前正方形裡是否數值完全相同(一開始是整個大正方形) 是的話直接回傳node，不是的話切割當前正方形為四象限每個象限再各自檢查是否數值相同 最後形成node，並加入子節點們，形成樹 Code class Solution { pu
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
Leetcode > Medium
#Leetcode #心得 #Hash Table #Depth-First Search #Breadth-First Search #Tree

450. Delete Node in a BST - Medium

前往題目 想法 找到目標後直接刪除，把parent直接接到他的子樹 思路但這樣的想法有點問題，因為沒有考慮到樹的右子樹必須要大於父節點 Recursion 遇到null直接回傳root，回傳null也行，反正都是同樣的值 接著就看當前節點是否是Key，大於的話就往左邊繼續搜尋，反之往右邊 如果找到同樣的值，只有左或者右一個子樹的時候直接捨棄當前節點，接上子樹就好 如果他同時有右子樹和左子樹，
Leetcode > Medium
#Leetcode #心得 #Binary Search Tree #Binary Tree #Tree

701. Insert into a Binary Search Tree - Medium

前往題目 想法 直接加在最後面？不知道怎麼處理balance的問題 思路這題根本無需balance，加到合理的地方就好了 Recusion直到null回傳新的節點，其包含新的值 如果當前父節點比較大，那就加到左子節點，否則右子節點 因為BST的特性，所以只會被加到樹裡一次 Code網友解答 class Solution { public TreeNode insertIn
Leetcode > Medium
#Leetcode #心得 #Binary Search Tree #Binary Tree #Tree