【寸铁的刷题笔记】树、dfs、bfs、回溯、递归(三)

【寸铁的刷题笔记】树、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、回溯

思路

思路：二叉搜索树的中序遍历是有序数组,顺序为：从小到大

左 int res = -1;//记录第K个数的节点值 int cnt = 0; //记录当前遍历到的节点个数 /* 思路：二叉搜索树的中序遍历是有序数组,顺序为：从小到大 左 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); } } /* 思想:根据定义,节点的左子树小于当前节点,节点的右子树大于当前节点 也就是left