二叉树刷题总结：二叉搜索树的属性

「这是我参与11月更文挑战的第13天，活动详情查看：2021最后一次更文挑战」

二叉搜索树中的搜索

题目

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

解题思路

二叉搜索树是一棵有序树，它有着以下的这些特征：

1. 左子树上的所有节点的值小于根节点的值；
2. 右子树上的所有节点的值大于根节点的值；

于是，我们可以用递归的方式来求解。

代码实现

java复制代码class Solution {
    // 递归，利用二叉搜索树特点
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        // 如果小于根节点
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
        // 反之
            return searchBST(root.right, val);
        }
    }
}

时间复杂度：O(H), H 为二叉搜索树的高度。

空间复杂度：O(H), 递归栈的深度为 H。

是不是二叉搜索树

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

解题思路

二叉搜索树有一特性是：在中序遍历下，输出的二叉搜索树节点的数值是一个有序序列。

于是，我们可以通过中序遍历的方式，来判断该序列是否是有序的，从而来判断该二叉树是否是一个有效的二叉树。

代码实现

java复制代码/**
 * 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 {
    public long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)){
            return false;
        }
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}

时间复杂度 : O(n)，其中 n 为二叉树的节点个数;

空间复杂度 : O(n)，其中 n 为二叉树的节点个数;

求二叉搜索树的最小绝对差

题目

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

解题思路

因为二叉搜索树是一棵有序树，通过中序遍历，我们可以得到一个有序数组，这就转化为在有序数组中求最值。

代码实现

java复制代码/**
 * 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 {
    int ans;
    int pre;
    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        pre = -1;
        inOrder(root);
        return ans;
    }

    public void inOrder(TreeNode node){
        if (node == null) {
            return;
        }
        inOrder(node.left);
        if (pre == -1) {
            pre = node.val;
        } else {
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
        }
        inOrder(node.right);
    }
}

时间复杂度：O(n)，其中 n 为二叉搜索树节点的个数。

空间复杂度：O(n), 递归栈的深度为节点数 n。

求二叉搜索树的众数

题目

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

解题思路

1. 对二叉搜索树进行中序遍历，这样就得到了一个有序数组；
2. 利用哈希表，来存储有序数组每个元素出现的次数，并记录次数最高的数值 maxLen；
3. 遍历哈希表，根据 maxLen，求得出现频率最高元素的合集；

代码实现

java复制代码/**
 * 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 {
    private List<Integer> list;
    public int[] findMode(TreeNode root) {
        list = new ArrayList();
        inOrder(root);

        Map<Integer, Integer> map = new HashMap();
        int maxLen = Integer.MIN_VALUE;
        for (int value :list) {
            map.put(value, map.getOrDefault(value, 0) + 1);
            if (maxLen < map.get(value)) {
                maxLen = map.get(value);
            } 
        }

        if (maxLen > 0) {
            List<Integer> ans = new ArrayList<>();
            for (int b:map.keySet()) {
                if (map.get(b).equals(maxLen)) {
                    ans.add(b);
                }
            }
            int answ[] = new int[ans.size()];
            for (int i = 0; i < ans.size(); i++) {
                answ[i] = ans.get(i);
            }
            return answ;
        }

        return new int[0];
    }

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

时间复杂度：O(n), 即遍历这棵树的复杂度。

空间复杂度：O(n), 即递归的栈空间的空间代价。

最后

好了，关于二叉搜索树的属性到这里就结束了。相信看完这篇文章，你会对二叉搜索树的属性有一定的了解，感谢你的阅读。

往期文章：

• StoreKit2 有这么香？嗯，我试过了，真香
• 看完这篇文章，再也不怕面试官问我如何构造二叉树啦！
• 那帮做游戏的又想让大家氪金，太坏了！
• 手把手带你撸一个网易云音乐首页 | 适配篇
• 手把手带你撸一个网易云音乐首页（三）
• 手把手带你撸一个网易云音乐首页（二）
• 手把手带你撸一个网易云音乐首页（一）
• 代码要写注释吗？写你就输了
• Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿
• iOS 优雅的处理网络数据，你真的会吗？不如看看这篇
• UICollectionView 自定义布局！看这篇就够了

请你喝杯 ☕️ 点赞 + 关注哦～

1. 阅读完记得给我点个赞哦，有👍 有动力
2. 关注公众号— HelloWorld杰少，第一时间推送新姿势

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有