代码随想录-Day22

2024-05-29 23:20
文章标签 随想录 代码 day22

本文主要是介绍代码随想录-Day22,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

方法一:两次遍历

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {List<TreeNode> path_p = getPath(root, p);List<TreeNode> path_q = getPath(root, q);TreeNode ancestor = null;for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {if (path_p.get(i) == path_q.get(i)) {ancestor = path_p.get(i);} else {break;}}return ancestor;}public List<TreeNode> getPath(TreeNode root, TreeNode target) {List<TreeNode> path = new ArrayList<TreeNode>();TreeNode node = root;while (node != target) {path.add(node);if (target.val < node.val) {node = node.left;} else {node = node.right;}}path.add(node);return path;}
}

这段代码定义了一个名为 Solution 的类,用于求解二叉搜索树(Binary Search Tree, BST)中两个指定节点的最近公共祖先(Lowest Common Ancestor, LCA)。类中包含两个方法:

  1. lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

    • 功能:该方法接收BST的根节点 root 和需要寻找LCA的两个节点 pq 作为参数,返回这两个节点的最近公共祖先。
    • 实现:首先,分别调用 getPath 方法获取节点 pq 到根节点的路径(以节点列表形式存储)。然后,遍历这两个路径,找到路径中最后一个相同的节点,即为最近公共祖先。如果两个路径没有共同节点(理论上在BST中不会发生,除非 pq 不在树中),则返回 null(虽然代码中未直接处理这种情况,但循环结束时 ancestor 仍为 null)。
  2. getPath(TreeNode root, TreeNode target)

    • 功能:该方法接收BST的根节点 root 和目标节点 target,返回从根到目标节点的路径上的所有节点列表。
    • 实现:通过一个循环不断比较当前节点与目标节点的值,决定是向左子树还是右子树移动。同时,将访问过的节点按路径顺序添加到列表 path 中。当找到目标节点时,将目标节点也添加到路径列表,并返回整个路径。

注意,这段代码的高效运行依赖于输入是二叉搜索树的特性,即树中任意节点的左子树所有节点的值都小于该节点的值,右子树所有节点的值都大于该节点的值。这使得在寻找特定值的节点时,可以快速地在树中进行定向移动,而不需要回溯,因此每个 getPath 方法的时间复杂度为O(log n),其中n是树中的节点数。整体的 lowestCommonAncestor 方法的时间复杂度也是O(log n),因为两个路径的最长公共前缀长度不会超过树的高度。

方法二:一次遍历

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {TreeNode ancestor = root;while (true) {if (p.val < ancestor.val && q.val < ancestor.val) {ancestor = ancestor.left;} else if (p.val > ancestor.val && q.val > ancestor.val) {ancestor = ancestor.right;} else {break;}}return ancestor;}
}

这段代码定义了一个名为 Solution 的类,其中包含一个方法 lowestCommonAncestor,用于在给定的二叉搜索树(BST)中找到两个指定节点 pq 的最近公共祖先(LCA)。这个方法直接利用了BST的性质(即左子树所有节点的值小于根节点值,右子树所有节点的值大于根节点值),以迭代而非递归的方式高效地解决了问题。以下是代码的详细解释:

  • 方法签名public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) 接受三个参数,分别是BST的根节点 root,以及需要找LCA的两个节点 pq

  • 初始化祖先节点:首先将 ancestor 初始化为根节点 root

  • 循环查找:进入一个 while 循环,循环条件默认为 true,意味着它将一直执行,直到通过 break 语句跳出循环。

    • 在循环内,首先检查 pq 的值与当前 ancestor 节点值的关系:
      • 如果 pq 的值都小于 ancestor 的值,说明它们都在当前节点的左子树中,因此将 ancestor 更新为其左子节点。
      • 如果 pq 的值都大于 ancestor 的值,说明它们都在当前节点的右子树中,因此将 ancestor 更新为其右子节点。
      • 如果以上两种情况都不满足,说明当前 ancestor 节点满足以下至少一种情况:
        • 它正好是 pq 中的一个。
        • 它位于 pq 之间,即一个在它的左子树,另一个在它的右子树,或者两者都在同一边但当前节点就是最近的共同祖先。
      • 在这种情况下,通过 break 退出循环,因为已经找到了最近公共祖先。
  • 返回结果:循环结束后,ancestor 节点即为所求的最近公共祖先,直接返回该节点。

这种方法的时间复杂度为 O(h),其中 h 是树的高度,因为在最坏情况下,我们可能需要从根节点一直走到 pq 中较深的那个节点。由于是二叉搜索树,高度 h 最坏情况下为 n(树退化为链表的情况),最好情况下为 log(n)。空间复杂度为 O(1),因为我们只使用了固定数量的指针变量,没有使用额外的空间来存储节点路径等。

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

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}TreeNode pos = root;while (pos != null) {if (val < pos.val) {if (pos.left == null) {pos.left = new TreeNode(val);break;} else {pos = pos.left;}} else {if (pos.right == null) {pos.right = new TreeNode(val);break;} else {pos = pos.right;}}}return root;}
}

这段代码定义了一个名为 Solution 的类,其中包含一个方法 insertIntoBST,该方法用于将一个值插入到给定的二叉搜索树(Binary Search Tree, BST)中。二叉搜索树的特性是:对于任意一个节点,其左子树中的所有节点的值都小于该节点的值,其右子树中的所有节点的值都大于该节点的值。以下是方法的逻辑解析:

  • 方法签名public TreeNode insertIntoBST(TreeNode root, int val) 接受两个参数,一个是BST的根节点 root,另一个是要插入的值 val

  • 基本情况处理:首先检查 root 是否为空。如果为空,说明当前树为空,那么直接创建一个新的 TreeNode,其值为 val,并返回这个新节点作为新树的根。

  • 寻找插入位置:如果根节点不为空,声明一个指针 pos 指向当前考虑的节点(初始化为根节点 root),然后进入一个 while 循环,用于找到插入新节点的位置。

    • 在循环中,如果 val 小于 pos 节点的值,则向左子树移动;如果 val 大于或等于 pos 节点的值,则向右子树移动。每次移动时,如果遇到空的子节点(即找到了插入位置),则在相应位置创建一个新节点,值为 val,并跳出循环。
  • 返回结果:循环结束后,无论是否插入新节点,根节点 root 的引用都保持不变,直接返回 root 即可。因为插入操作是在原有的树结构基础上进行的,没有改变根节点本身,只是在其某个子树上新增了节点。

这种方法保持了二叉搜索树的性质,插入操作的时间复杂度在最坏情况下为 O(H),其中 H 是树的高度。对于平衡的二叉搜索树,平均情况下插入操作的时间复杂度为 O(log N),N 为树中节点的数量。

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

方法一:递归

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}if (root.val > key) {root.left = deleteNode(root.left, key);return root;}if (root.val < key) {root.right = deleteNode(root.right, key);return root;}if (root.val == key) {if (root.left == null && root.right == null) {return null;}if (root.right == null) {return root.left;}if (root.left == null) {return root.right;}TreeNode successor = root.right;while (successor.left != null) {successor = successor.left;}root.right = deleteNode(root.right, successor.val);successor.right = root.right;successor.left = root.left;return successor;}return root;}
}

这段代码定义了一个名为 Solution 的类,其中包含一个方法 deleteNode,用于在给定的二叉搜索树(BST)中删除具有给定值的节点。二叉搜索树的特性是左子树中的所有节点的值小于当前节点值,右子树中的所有节点的值大于当前节点值。下面是代码逻辑的详细解析:

  1. 基本情况处理:首先检查根节点是否为空,如果为空,则直接返回 null,表示树为空或目标节点不存在。

  2. 查找目标节点:利用BST的性质进行查找。如果目标值 key 小于当前节点值 root.val,则在左子树中递归删除;如果 key 大于当前节点值,则在右子树中递归删除。这一步骤会一直进行到找到目标节点或递归到空节点为止。

  3. 删除目标节点

    • 当找到目标节点(即 root.val == key)时,有三种情况:
      • 叶子节点:如果目标节点没有左右子节点,直接返回 null,让其父节点指向 null 达到删除效果。
      • 仅有一个子节点:如果目标节点只有左子节点或右子节点,直接返回其非空的子节点,使父节点指向这个子节点。
      • 有两个子节点:找到目标节点的后继节点(即右子树中的最小节点 successor),用后继节点替换当前目标节点。然后在右子树中递归删除这个后继节点(因为后继节点可能是其所在子树的最小值,也可能有右子节点,故需要递归删除以保持BST性质)。后继节点的左子树挂载到原目标节点的左子树上,原目标节点的右子树挂载到后继节点的右子树上,这样既删除了目标节点,又保持了BST的结构。
  4. 返回处理结果:在递归的每一步中,直接返回处理后的子树根节点,这样可以保证上一层递归能够正确接收到更新后的子树状态。

通过上述逻辑,该方法能够有效地在二叉搜索树中删除指定值的节点,同时保持树的二叉搜索特性。

这篇关于代码随想录-Day22的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1014921

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can