当前位置: 首页 > news >正文

day22 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点

问题:

● 235. 二叉搜索树的最近公共祖先
● 701.二叉搜索树中的插入操作
● 450.删除二叉搜索树中的节点

首先,二叉搜索树是一种常见的数据结构,它具有以下特点:

  1. 每个节点最多有两个子节点,分别为左子节点和右子节点;
  2. 左子节点的值小于父节点的值,右子节点的值大于父节点的值;
  3. 没有重复的节点值。

在刷题过程中,我遇到了以下三道题目:

    1. 二叉搜索树的最近公共祖先:该题目要求在一个二叉搜索树中,找到两个节点的最近公共祖先。我的解题思路是,从根节点开始遍历二叉搜索树,如果两个节点的值都小于当前节点的值,说明它们都在当前节点的左子树中;如果两个节点的值都大于当前节点的值,说明它们都在当前节点的右子树中;如果一个节点的值小于当前节点的值,另一个节点的值大于当前节点的值,说明它们的最近公共祖先就是当前节点。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。
    1. 二叉搜索树中的插入操作:该题目要求在一个二叉搜索树中插入一个节点。我的解题思路是,从根节点开始遍历二叉搜索树,如果插入节点的值小于当前节点的值,就去遍历左子树;如果插入节点的值大于当前节点的值,就去遍历右子树。一直遍历到某个节点的左子节点或右子节点为空时,就把插入节点作为该节点的左子节点或右子节点。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。
    1. 删除二叉搜索树中的节点:该题目要求在一个二叉搜索树中删除一个节点。我的解题思路是,首先找到要删除的节点,如果该节点有两个子节点,就找到它的后继节点(即右子树中最小的节点),把后继节点的值复制到要删除的节点中,然后把要删除的节点变成后继节点;如果该节点只有一个子节点或没有子节点,就直接把该节点删除,并把它的子节点接到它的父节点上。具体实现可以使用递归或者迭代方式,时间复杂度为O(logn)。

总结一下,二叉搜索树是一种非常重要的数据结构,在刷题过程中,我对它的特点和操作有了更深入的理解。对于二叉搜索树的操作,递归和迭代实现都可以,具体选择哪种方式要根据具体情况而定。在Java中,可以使用TreeNode类来表示二叉树节点,具体实现可以参考以下代码:

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {return root;}if (root.val > p.val && root.val > q.val) {return lowestCommonAncestor(root.left, p, q);} else if (root.val < p.val && root.val < q.val) {return lowestCommonAncestor(root.right, p, q);} else {return root;}}public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (val < root.val) {root.left = insertIntoBST(root.left, val);} else {root.right = insertIntoBST(root.right, val);}return root;}public TreeNode deleteNode(TreeNode root, int key) {if (root == null) {return null;}if (key < root.val) {root.left = deleteNode(root.left, key);} else if (key > root.val) {root.right = deleteNode(root.right, key);} else {if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;} else {TreeNode minNode = getMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}}return root;}public TreeNode getMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}
http://www.lryc.cn/news/56149.html

相关文章:

  • ChatGPT 这个风口,普通人怎么抓住?
  • Python代码规范:企业级代码静态扫描-代码规范、逻辑、语法、安全检查,以及代码规范自动编排(2)
  • acme.sh从 letsencrypt 生成SSL免费证书并自动更新证书
  • 基于html+css的evenly布局
  • 【从零开始学习 UVM】10.5、UVM TLM —— UVM TLM Blocking Get Port
  • English Learning - L2 第 10 次小组纠音 辅音 [m] [n] [ŋ] 半元音 [w] [j] 2023.3.29 周三
  • 从零开始实现一个C++高性能服务器框架----环境变量模块
  • git常用命令的解释
  • DNS和CDN的区别与联系
  • Java基础知识 | 常见面试题(中):面向对象基础
  • 勒索软件正在从 Windows 转向 Linux
  • 信息系统项目管理师 第11章 项目成本管理
  • XML 简介
  • ERP:华为杀入,金蝶们打颤?
  • Linux——总复习1
  • 控制SQL*PLUS的环境和数据字典简介
  • Chapter11.3:MATLAB_SIMULINK在离散系统中的应用
  • 过滤器Filter
  • MySQL数据同步ES的常用思路和方法
  • spring源码之扫描前设置
  • C++ 98/03 应该学习哪些知识19
  • java毕业生就业信息管理系统servlet程序
  • linux命令-netstat
  • 微服务+springcloud+springcloud alibaba学习笔记【Rest微服务工程搭建】(2/9)
  • 【Redis7】Redis7 十大数据类型
  • java 死锁怎么解决, 盘它
  • 【新2023Q2押题JAVA】华为OD机试 - 服务依赖
  • 交友项目【通用设置】三个功能实现
  • MongoDB 更新文档(更新多条文档)
  • ubuntu20 qt6.4.3 ustc镜像安装 xdma