LeetCode刷题Day16——二叉搜索树(搜索、验证、最小绝对差、众数)

简介: 一、二叉搜索树中的搜索题目链接:700. 二叉搜索树中的搜索

一、二叉搜索树中的搜索

题目链接:700. 二叉搜索树中的搜索

/**
 * <pre>
 * 1.递归
 * 2.迭代
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 14:33
 */
public class 二叉搜索树中的搜索700 {
    public static 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);
        }
    }
    public static TreeNode searchBST2(TreeNode root, int val) {
        while (root != null) {
            if (root.val == val) {
                return root;
            } else if (val < root.val) {
                root = root.left;
            } else {
                root = root.right;
            } 
        }
        return null;
    }
}

二、验证二叉搜索树

题目链接:98. 验证二叉搜索树

/**
 * <pre>
 * 1.递归,每次判断根据上下限判断当前节点是否满足条件
 * 2.中序遍历:二叉搜索树中序遍历后的顺序为从小到大
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 16:21
 */
public class 验证二叉搜索树98 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val >= upper || node.val <= lower) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long inorder = Long.MIN_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            if (pop.val <= inorder) { // 二叉搜索树中序遍历的节点应该越来越大
                return false;
            }
            inorder = pop.val;
            root = pop.right;
        }
        return true;
    }
}

三、二叉搜索树的最小绝对差

题目链接:530. 二叉搜索树的最小绝对差

/**
 * <pre>
 * 1.中序遍历,出来的结果是升序排序,插值最小肯定存在在两个相邻元素之间
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 16:58
 */
public class 二叉搜索树的最小绝对差530 {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        long last = Integer.MIN_VALUE, ans = Integer.MAX_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            ans = Math.min(ans, pop.val - last);
            last = pop.val;
            root = pop.right;
        }
        return (int)ans;
    }
}

四、二叉搜索树中的众数

题目链接:501. 二叉搜索树中的众数

/**
 * <pre>
 * 1.中序遍历
 * </pre>
 *
 * @author <a href="https://github.com/Ken-Chy129">Ken-Chy129</a>
 * @date 2023/1/17 17:29
 */
public class 二叉搜索树中的众数501 {
    public int[] findMode(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        int maxCount = 0, count = 0, last = Integer.MIN_VALUE;
        while (!stack.empty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            if (last == pop.val) {
                count++;
            } else {
                count = 1;
            }
            if (maxCount == count) {
                list.add(pop.val);
            } else if (maxCount < count) {
                list.clear();
                list.add(pop.val);
                maxCount = count;
            }
            last = pop.val;
            root = pop.right;
        }
        int[] res = new int[list.size()];
        for (int i=0; i<list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
相关文章
|
6天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
8 1
|
25天前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
9 1
|
25天前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
13 1
|
25天前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
34 0
|
25天前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
8 0
|
25天前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
10 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口