【寸鐵的刷題筆記】樹、dfs、bfs、回溯、遞歸(三)
大家好 我是寸鐵👊
金三銀四，樹、dfs、bfs、回溯、遞歸是必考的知識點?
快跟著寸鐵刷起來！面試順利上岸👋
喜歡的小伙伴可以點點關注 💝
530. 二叉搜索樹的最小絕對差
考點
DFS、雙指針
思路
思路：雙指針,一個指針用于記錄當前的節點(回溯時的當前節點),一個指針用于記錄上一個節點。
不斷更新兩個指針的值的差值的最小值即可
代碼
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {/*思路：雙指針,一個指針用于記錄當前的節點(回溯時的當前節點),一個指針用于記錄上一個節點。不斷更新兩個指針的值的差值的最小值即可*/TreeNode pre; //記錄上一個遍歷的節點int result = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {if(root == null)return 0;traversal(root);return result;}public void traversal(TreeNode root){if(root == null)return; // 遍歷到最后一個節點時,終止,向上回溯//左traversal(root.left);//中if(pre != null){result = Math.min(result , root.val - pre.val);}//一開始時,pre為空節點,遞歸到最后一個節點時,記錄當前的節點//向上回溯時,pre為上一個節點,root為此時的節點,做差即可//當pre不為空時,再進行做差取最小值操作。pre = root;//右traversal(root.right);}
}
230. 二叉搜索樹中第K小的元素
考點
DFS、回溯
思路
思路：二叉搜索樹的中序遍歷是有序數組,順序為：
從小到大
左<中<右,根據這一點,先遍歷左子樹,判斷遍歷到的節點的數量cnt是否等于k
如果cnt等于k,則說明這個節點就是第k個節點。
代碼
class Solution {int res = -1;//記錄第K個數的節點值int cnt = 0; //記錄當前遍歷到的節點個數/*思路：二叉搜索樹的中序遍歷是有序數組,順序為：從小到大左<中<右,根據這一點,先遍歷左子樹,判斷遍歷到的節點的數量是否等于k如果等于,則說明這個節點就是第k個節點。*/public int kthSmallest(TreeNode root, int k) {dfs(root , k);return res;//res全局變量,直接返回res即可。}public void dfs(TreeNode root, int k){if(root == null)return;//直接結束//左子樹dfs(root.left , k);//注意:這里是第k個 從1開始,cnt要先++if(++cnt == k){res = root.val;return;//一種理解是函數直接結束//一種理解是向上回溯,把結果返回給根節點。}//右子樹dfs(root.right , k);}
}98. 驗證二叉搜索樹
考點
DFS、雙指針、回溯
與 530. 二叉搜索樹的最小絕對差的處理邏輯類似
思路
思想:根據定義,節點的左子樹
小于當前節點,節點的右子樹大于當前節點
也就是left < middle < right
很自然的就想到了用中序遍歷,再判斷一下是否滿足left < middle < right即可
進一步,我們只需要判斷當前的節點是否小于之前的節點。
如果小于則不滿足條件,向上返回false即可。
否則，則滿足條件。
代碼
class Solution {/*思想:根據定義,節點的左子樹小于當前節點,節點的右子樹大于當前節點也就是left < middle < right很自然的就想到了用中序遍歷,再判斷一下是否滿足left < middle < right即可進一步,我們只需要判斷當前的節點是否小于之前的節點。如果小于則不滿足條件,向上返回false即可。否則，則滿足條件。*/TreeNode pre; //存儲上一個節點public boolean isValidBST(TreeNode root) {//如果節點為空則直接返回trueif(root == null)return true;//左 創建一個變量記錄左子樹遞歸的結果boolean left = isValidBST(root.left);if(!left){return false;}//中 處理條件的邏輯 判斷當前節點是否 <= 上一個節點if(pre != null && root.val <= pre.val){return false;}//一開始為空,記錄上一個節點。pre = root;//右 創建一個變量記錄右子樹遞歸的結果boolean right = isValidBST(root.right);//向上返回右子樹遞歸的結果 right// if(!right){// return false;// }//與下等效,考慮到方法的返回語句,如下編譯通過。return right;}
}
看到這里的小伙伴，恭喜你又掌握了一個技能👊
希望大家能取得勝利，堅持就是勝利💪
我是寸鐵！我們下期再見💕
往期好文💕
保姆級教程
【保姆級教程】Windows11下go-zero的etcd安裝與初步使用
【保姆級教程】Windows11安裝go-zero代碼生成工具goctl、protoc、go-zero
【Go-Zero】手把手帶你在goland中創建api文件并設置高亮
報錯解決
【Go-Zero】Error: user.api 27:9 syntax error: expected ‘:‘ | ‘IDENT‘ | ‘INT‘, got ‘(‘ 報錯解決方案及api路由注意事項
【Go-Zero】Error: only one service expected goctl一鍵轉換生成rpc服務錯誤解決方案
【Go-Zero】【error】 failed to initialize database, got error Error 1045 (28000):報錯解決方案
【Go-Zero】Error 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)報錯解決方案
【Go-Zero】type mismatch for field “Auth.AccessSecret“, expect “string“, actual “number“報錯解決方案
【Go-Zero】Error: user.api 30:2 syntax error: expected ‘)‘ | ‘KEY‘, got ‘IDENT‘報錯解決方案
【Go-Zero】Windows啟動rpc服務報錯panic:context deadline exceeded解決方案
Go面試向
【Go面試向】defer與time.sleep初探
【Go面試向】defer與return的執行順序初探
【Go面試向】Go程序的執行順序
【Go面試向】rune和byte類型的認識與使用
【Go面試向】實現map穩定的有序遍歷的方式
