代码随想录刷题|LeetCode 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先

简介: 代码随想录刷题|LeetCode 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先

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

题目链接:力扣

思路

二叉搜索树是有序的。遇到在二叉搜索树上求什么最值,差值之类的,就把他想成在一个有序数组上求最值,求差值,这样就简单多了


       二叉搜素树采用中序遍历就是一个有序数组


       在一个有序数组上求两个数最小差值,就比较简单了


       最直观的想法,就是把二叉搜索树转换成有序数组,然后遍历一遍数组,就统计出来最小差值了


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

借用数组

       借用数组,将二叉树按照中序遍历一一添加到数组中,在数组中寻找最小差值      

class Solution {
    List<Integer> listVal = new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        int result = Integer.MAX_VALUE;     
        for (int i = 1; i < listVal.size(); i++) {
            int val = listVal.get(i) - listVal.get(i - 1);
            if (val < result) {
                result = val;
            }
        }
        return result;
    }
    public void traversal(TreeNode node) {
        if (node ==  null) {
            return;
        }
        // 左
        traversal(node.left);
        // 中
        listVal.add(node.val);
        // 右
        traversal(node.right);
    }
}

直接递归

       两个指针指向,在cur离开最小值的之后给pre进行赋值,此后,两个指针紧紧相随


87e14621185a4f9a936e7f29d76f07d1.png

class Solution {
    // 定义结果变量
    int result = Integer.MAX_VALUE;
    // 定义指针
    TreeNode pre = null;
    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return result;
    }
    void traversal (TreeNode cur) {
        if (cur == null) {
            return;
        }
        // 左
        traversal(cur.left);
        // 中
        if (pre != null) {
            result = Math.min(result, cur.val - pre.val);
        }
        pre = cur;
        // 右
        traversal(cur.right);
    }
}

501.二叉搜索树中的众数

题目链接:力扣

思路


最直接的思路就是遍历整个二叉搜索树,同时用Map通知每个数字出现的次数,返回频率最高的数字的结果集,这样无疑是比较复杂的


       再者,就是首先遍历一次二叉树,然后统计数字出现的最高频率。然后再遍历一次二叉树,找到出现频率最高的元素


       这种遍历使用双指针遍历两次二叉树的做法还是比较复杂,如果在一次遍历中就将记录每个数字出现的频率、记录出现的最高频率数字,这两件事情同时一起做了呢?


       那就是遍历相同节点的元素的时候给节点元素记录出现频率+1,并且如果记录的值等于目前统计的最大频率的时候就记录,就将元素添加进结果集。如果记录的新的count值大于目前统计的最大频率maxCount了,那就说明之前记录的数字都是不合适的,全部删除了,重新记录


二叉搜索树中的众数

class Solution {
    List<Integer> result;
    TreeNode pre;
    int count;
    int maxCount;
    public int[] findMode(TreeNode root) {
        pre = null;
        count = 0;
        maxCount = 0;
        result = new ArrayList<>();
        traversal(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }
    void traversal(TreeNode cur) {
        // 终止条件
        if (cur == null) {
            return;
        }
        // 左
        traversal(cur.left);
        // 中 
        if (pre == null || pre.val != cur.val) {   // 这两种情况下count要从头开始记录,默认应该为1
            count = 1;
        } else if (pre.val == cur.val) {  // 当相等的时候,count进行记录
            count++;
        } 
        // 当count在不断记录的时候,也要时刻关注maxCount这边
        if (count == maxCount) {
            result.add(cur.val);
        } else if (count > maxCount) {
            maxCount = count;
            result.clear();
            result.add(cur.val);
        }
        // pre指针进行移动
        pre = cur;
        // 右
        traversal(cur.right);
    }
}

236. 二叉树的最近公共祖先

题目链接:力扣

思路

已经触及目前我的理解上限了,就是很妙,就是很绝,思路就是很棒,很清楚,不得不感叹,今天跟着视频听了一遍,巧了两遍代码,稍微理解了


       首先题目要求中确保p和q都在二叉树中


       我们要寻找的是公共祖先,也就是我们要查找的这个祖先肯定是有自己的左节点和右节点的,所以是在中间节点上进行逻辑处理,所以采用的遍历方式是左右中


       接下来就是分析q和p出现的所有情况:

               1、p和q属于公共祖先的子树上的元素

                       1).一个在公共祖先的左子树上,一个在公共祖先的右子树上

                       2).两个都在公共祖先的左子树上

                       3).两个都在公共祖先的右子树上

               2、p或q一个是公共祖先本身

b52cc0f1efb94ff2aebea23e3bdf7ffc.png

其实情况1就将所有的情况2的情况就包含了


       情况1的三种情况对节点返回结果处理的三种情况:

               1、left != null && right != null

               2、left != null && right == null

               3、left == null && right != null

       如果左右都不是空,那说明左右子树分别找到了一个节点,那该节点就是公共祖先了

       如果左空右不空,那说明右边已经找到了公共祖先了,返回右节点带回来的就可以

       如果右空左不空,那说明左边已经找到了公共祖先了,返回左节点带回来的就可以

二叉树的最近公共祖先

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