代码随想录算法训练营第二十一天 | LeetCode 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点

简介: 代码随想录算法训练营第二十一天 | LeetCode 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点

1. LeetCode 235. 二叉搜索树的最近公共祖先

1.1 思路

  1. 在普通二叉树中搜索最近公共祖先是用了后序遍历,然后一层一层返回。本题是二叉搜索树,可以利用它的特性,如果p和q都比根节点小,那说明最近公共祖先一定在左子树。如果p和q都比根节点大,那说明最近公共祖先一定在右子树。那找到了一个节点在p和q之间,那就是公共节点了,并且一定是最近的了,因为是二叉树,再往下不管是左还是右都分开了
  2. 递归函数的参数和返回值:返回值就是节点,参数就是root,p,q。都是题目的
  3. 终止条件:遇到空就返回空
  4. 单层递归的逻辑:因为这题本来就是有序的,而且不涉及中间节点的处理,就不管前中后序了,只需要有左和右即可。如果root比p和q的都大,就向左搜索,left=travelsal(root.left, p, q),如果left不为空就说明left就是最近公共祖先了,就返回left。如果root比p和q的都小,就向右搜索,right=travelsal(root.right, p, q),如果right不为空就说明right就是最近公共祖先了,就返回right。剩下的情况就是最近公共祖先root在p和q之间了,就直接return root。

1.2 代码

//
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }
        if(root.val>p.val&&root.val>q.val){
            TreeNode left=lowestCommonAncestor(root.left,p,q);
            if(left!=null){
                return left;
            }
        }
        if(root.val<p.val&&root.val<q.val){
            TreeNode right=lowestCommonAncestor(root.right,p,q);
            if(right!=null){
                return right;
            }
        }
        return root;
    }
}

2. LeetCode 701. 二叉搜索树中的插入操作

2.1 思路

  1. 在二叉搜索树中插入任何一个节点的话,在叶子节点都能找到它的位置。所以是找到一个叶子节点插入即可,依然保持二叉树的有序性
  2. 递归函数的参数和返回值:返回值节点node,参数就是root,val
  3. 终止条件:如果遇到空,就找到插入节点的位置了,就是叶子节点了。就创建节点node然后放入val,然后返回node。因为是一层一层向下遍历,返回的时候就是把节点返回给上面遍历下来的那个节点
  4. 单层递归的逻辑:如果节点值比val大,就向左遍历,就用root.left接收函数(root.left, val)的返回值,作为root的左孩子。如果节点值比val小,就向右遍历,就用root.right接收函数(root.right, val)的返回值,作为root的右孩子。举例这里如果递归到了最后一层的叶子节点,叶子节点插入的新节点就返回给此时的root,root就作为新节点的父节点,二叉树就连接起来了。最后return root;就是一层一层返回给最终新的二叉树的根节点了。

2.2 代码

//
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) // 如果当前节点为空,也就意味着val找到了合适的位置,此时创建节点直接返回。
            return new TreeNode(val);
        if (root.val < val){
            root.right = insertIntoBST(root.right, val); // 递归创建右子树
        }else if (root.val > val){
            root.left = insertIntoBST(root.left, val); // 递归创建左子树
        }
        return root;
    }
}

3. LeetCode 450. 删除二叉搜索树中的节点

3.1 思路

  1. 这题要求删除节点后依然保证仍是一棵二叉搜索树
  2. 先分析有什么情况:①没找到要删的节点;其余四种情况就是找到了要删的节点②要删除的节点左右都为空,即这个节点是叶子节点;③这个节点不是叶子节点,左不为空右为空,就直接让其左孩子变为其父节点的左孩子;④这个节点不是叶子节点,左为空右不为空,就直接让其右孩子变为其父节点的右孩子;⑤左不为空右也不为空,这种情况需要大幅调整结构了。删除这个节点后要么就是让左孩子继位,要么就是让右孩子继位,举例假设让右孩子继位,左孩子就只能放在原右孩子的左子树中最左侧的位置(这个数是仅仅比被删节点大一点点的,就刚刚能让原左孩子作为这个节点的左孩子,这里可能不好理解,看视频的6分钟左右),放完以后,在删除节点以后,直接让被删除节点的父节点指向右孩子
  3. 递归函数的返回值和参数:定义函数就是原题的函数,返回的是新的二叉搜索树的根节点
  4. 终止条件:遍历找到要删除的节点。因为这题不需要遍历整棵二叉树,重点在删除节点的逻辑,因此删除的操作是放在终止条件中。
  5. 第1种情况,就是遍历到空了也没找到,就返回null;
  6. 第2种情况,是叶子节点(左右都为空),就直接return null,这个null是由原节点的父节点接收,因为在代码最下面会有当前层的左子树=下一层递归的返回值以及右子树=下一层递归的返回值;
  7. 第3种情况,左不为空右为空,就让被删节点的父节点接收其左孩子,就是返回root.left,被删节点的父节点会接收住的
  8. 第4种情况,左为空右不为空,就让被删节点的父节点接收其右孩子,就是返回root.right,被删节点的父节点会接收住的
  9. 第5种情况就else了,(已上面的例子以右孩子继位为例)先找到被删节点的右子树的最左侧的值,只有这个数是仅仅比被删节点大一点点的,(这里已经遍历到了被删节点)首先定义个cur=root.right,然后向左遍历去到叶子节点,while(cur.left!=null) cur=cur.left;然后让cur.left=root.left,即这个叶子节点的左子树等于被删节点的左子树了。然后就是删除那个节点了,此时的处理逻辑就是左为空右不为空(第4种情况)的处理逻辑了,就return root.right。如果是让左孩子继位就可以自己画图看看
  10. 单层递归的逻辑:如果key<root.val就向左遍历搜索,root.left=delete(root.left, val);如果key>root.val就向右遍历搜索,root.right=delete(root.right, val);这里用节点的左右孩子接收的就是删除节点后返回的节点。最后左右子树处理完了就return root

3.2 代码

//
class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return root;
    if (root.val == key) {
      if (root.left == null) {
        return root.right;
      } else if (root.right == null) {
        return root.left;
      } else {
        TreeNode cur = root.right;
        while (cur.left != null) {
          cur = cur.left;
        }
        cur.left = root.left;
        root = root.right;
        return root;
      }
    }
    if (root.val > key) root.left = deleteNode(root.left, key);
    if (root.val < key) root.right = deleteNode(root.right, key);
    return root;
  }
}
目录
打赏
0
0
0
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
6月前
|
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
94 7
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等