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
701. Insert into a Binary Search Tree - Medium 前往題目 想法 直接加在最後面?不知道怎麼處理balance的問題 思路這題根本無需balance,加到合理的地方就好了 Recusion直到null回傳新的節點,其包含新的值 如果當前父節點比較大,那就加到左子節點,否則右子節點 因為BST的特性,所以只會被加到樹裡一次 Code網友解答 class Solution { public TreeNode insertIn 2024-10-24 Leetcode > Medium #Leetcode #心得 #Binary Search Tree #Binary Tree #Tree
606. Construct String from Binary Tree - Medium 前往題目 想法 Preorder的順序,然後在數字左右加上括號 思路 Preorder順序 刻意跳過leaf的左右子節點,否則會加無謂的括號 建立左子樹 建立右子樹,但只有右子樹不為空才建立 Code第一次寫出來沒考慮到遇到leaf要直接回傳,否則會加入空的括號 class Solution { StringBuilder res; public String tr 2024-10-23 Leetcode > Medium #Leetcode #心得 #String #Binary Tree #Depth-First Search #Tree
2331. Evaluate Boolean Binary Tree - Easy 前往題目 想法 DFS,根據情況賦予0或1 思路Recursion 遇到null就回傳false 然後記錄左右子節點的布林值 如果當前節點為OR就把當前的值改為left || right的結果 AND也是一樣 最後回傳當前節點的布林值 Codeclass Solution { public boolean evaluateTree(TreeNode root) { 2024-10-22 Leetcode > Easy #Leetcode #心得 #Binary Tree #Depth-First Search #Tree
3325. Count Substrings With K-Frequency Characters I - Medium 前往題目 想法 sliding window直接暴力解 思路Weekly contest 420的題目 左指針固定,右指針移動,每次都檢查當前字母數量是否大於等於k 如果是的話更新結果,之後移動右指針也繼續結果+1,因為都還包含在內所以一定>=k 右指針走到盡頭時,左指針往右移動一步,右指針重新初始化,重新一步一步展開window Codeclass Solution { 2024-10-22 Leetcode > Medium #Leetcode #心得 #String #Hash Table #Sliding Window
3324. Find the Sequence of Strings Appeared on the Screen - Medium 前往題目 想法 先把第一個字母當基準點準備好,再來就直接循環建立剩餘的字母 思路weekly contest 420的題目 完賽後再看一遍其實直接循環建立就好 循環把字母建立好 先放入a,然後加到結果,接著比較字母是否和目標的一樣,不是的話ascii + 1再加入結果再比較 Codeclass Solution { public List<String> strin 2024-10-22 Leetcode > Medium #Leetcode #心得 #String #Simulation