刷题笔记（十七）--二叉搜索树：关于属性问题

系列文章目录

刷题笔记（一）–数组类型：二分法
刷题笔记（二）–数组类型：双指针法
刷题笔记（三）–数组类型：滑动窗口
刷题笔记（四）–数组类型：模拟
刷题笔记（五）–链表类型：基础题目以及操作
刷题笔记（六）–哈希表：基础题目和思想
刷题笔记（七）–字符串：经典题目
刷题笔记（八）–双指针：两数之和以及延伸
刷题笔记（九）–字符串：KMP算法
刷题笔记（十）–栈和队列：基础题目
刷题笔记（十一）–栈和队列：Top-K问题
刷题笔记（十二）–复习：排序算法
刷题笔记（十三）–二叉树：前中后序遍历（复习）
刷题笔记（十四）–二叉树：层序遍历和DFS,BFS
刷题笔记（十五）–二叉树：属性相关题目
刷题笔记（十六）–二叉树：修改与构造

前言

这里就是关于二叉搜索树了，我是不是应该把红黑树提上日程了？emmmmm，应该是的，好好加油。

题录

700. 二叉搜索树中的搜索

题目链接如下：

700. 二叉搜索树中的搜索

题目截图如下：

方法一：直接遍历

这种的话就是把这个二叉搜索树当做普通的树来进行操作就行。

public class 二叉搜索树中的搜索_方法一 {
    
    //你可以直接遍历整个树，最后得到值等于val的节点
    TreeNode node;
    public TreeNode searchBST(TreeNode root, int val) {
    
        solve(root,val);
        return node;
    }

    public void solve(TreeNode root, int val){
    
        if(root == null) return;
        if(root.val == val) node = root;
        solve(root.left,val);
        solve(root.right,val);
    }

}

方法二：根据性质遍历_递归写法

这种的话就是根据二叉搜索树的性质进行遍查找

二叉搜索树的性质：左子树所有节点的值小于根节点，根节点的值小于右子树的所有节点值

public class 二叉搜索树中的搜索_方法二 {
    
    //你也可以根据二叉搜索树的性质去进行搜索,递归写法
    public TreeNode searchBST(TreeNode root, int val) {
    
        return solve(root,val);
    }

    public TreeNode solve(TreeNode root,int val){
    
        if(root == null) return null;
        if(root.val == val)  return root;
        if(root.val > val) return solve(root.left,val);
        return solve(root.right,val);
    }
}

方法三：根据性质遍历_迭代写法

public class 二叉搜索树中的搜索_方法三 {
    
    //你也可以根据二叉搜索树的性质去进行搜索,迭代写法
    public TreeNode searchBST(TreeNode root, int val) {
    
        if(root == null) return null;
        while(root != null){
    
            if(root.val == val){
    
                return root;
            }else if(root.val > val){
    
                root = root.left;
            }else{
    
                root = root.right;
            }
        }
        return null;
    }
}

98. 验证二叉搜索树

题目链接如下：

98. 验证二叉搜索树

题目截图如下：

这里的话可以用到二叉搜索树的另外一个性质：

二叉搜索树的中序遍历结果是一个递增数组

方法一：中序遍历数组接收

public class 验证二叉搜索树_方法一 {
    
    //二叉搜索树的性质是什么？是不是前序遍历是一个递增的数组？所以嘛，中序遍历，然后用数组存储，这感觉不就来了？
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root){
    
        solve(root);
        if (list.size() == 1) return true;
        for (int i = 1; i < list.size(); i++) {
    
            if(list.get(i - 1) > list.get(i)){
    
                return false;
            }
        }
        return true;
    }

    public void solve(TreeNode node){
    
        if(node == null) return;
        solve(node.left);
        list.add(node.val);
        solve(node.right);
    }
}

方法二：利用性质遍历

public class 验证二叉搜索树_方法二 {
    
    //这种的话还是一个中序遍历，但是有一点点的不同

    public boolean isValidBST(TreeNode root) {
    
        return solve(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean solve(TreeNode node,long min,long max){
    
        if(node == null) return true;
        if(node.val < min || node.val > max) return false;
        return solve(node.left,min,node.val) && solve(node.right,node.val,max);
    }
}

530. 二叉搜索树的最小绝对差

题目链接如下：

530. 二叉搜索树的最小绝对差

题目截图如下：

方法一

这种的话就是在遍历的过程中记录上一个节点的值，然后不断更新这个值。

public class 二叉搜索树的最小绝对差_方法一 {
    
    int sum = Integer.MAX_VALUE;//用来保存最小的差值
    int preVal = -100000;//用来保存前一个节点的值
    public int getMinimumDifference(TreeNode root) {
    
        solve(root);
        return sum;
    }

    public void solve(TreeNode root){
    
        if(root == null) return;
        if(root.left != null) solve(root.left);
        if(Math.abs(root.val - preVal) < sum){
    
            sum = Math.abs(root.val - preVal);
        }
        preVal = root.val;
        if(root.right != null) solve(root.right);
    }
}

方法二

这种的话就很好理解哈，根据

public class 二叉搜索树的最小绝对差_方法二 {
    
    public int getMinimumDifference(TreeNode root) {
    
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < list.size() - 1;i++){
    
            int key = Math.abs(list.get(i) - list.get(i + 1));
            if(key < min) min = key;
        }
        return min;
    }

    public void inOrder(TreeNode node,List<Integer> list){
    
        if(node == null) return;
        inOrder(node.left,list);
        list.add(node.val);
        inOrder(node.right,list);
    }
}

501. 二叉搜索树中的众数

题目链接如下：

501. 二叉搜索树中的众数

题目截图如下：

看我代码标注吧

public class 二叉搜索树中的众数 {
    
    //这道题的话我唯一的想法就是遍历二叉搜索树，然后用哈希表保存对应关系
    //或者这样搞，我不用数组来维护，我用两个数字来进行维护
    int maxNum;//记录当前出现最多的次数
    int num;//因为中序遍历数组的众数一定是一个连续的数组，所以如果num是记录当前数字的
    int count;//记录当前数字出现的次数
    List<Integer> list = new ArrayList<>();//用来记录出现次数最多的数字

    public int[] findMode(TreeNode root) {
    
        inOrder(root);
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
    
            arr[i] = list.get(i);
        }
        return arr;
    }

    public void inOrder(TreeNode node){
    
        if(node == null) return;
        inOrder(node.left);
        solve(node);
        inOrder(node.right);
    }

    public void solve(TreeNode node){
    
        //首先就是要验证当前节点和记录的节点值是否相同
        if(node.val != num) {
    
            num = node.val;
            count = 1;
        }else {
    
            count++;
        }
        //然后根据信息决定是否要更新值
        if(count > maxNum){
    
            maxNum = count;
            list.clear();
            list.add(node.val);
        }else if(count == maxNum){
    
            list.add(node.val);
        }
    }
}

总结

加快进度！！！