LeetCode——二叉树篇(八)

刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com

目录

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

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

         迭代

递归

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

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

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 *(思路:对于一个结点,只要其左子树出现p或q,或右子树出现p或q,那么该节点就是节点p和q的最近公共                    
    祖先;
 *如果递归遍历遇到q,就将q返回,遇到p就将p返回,那么如果左右子树的返回值都不为空,说明此时的中节 
    点,一定是q和p的最近祖先。
 *
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归结束条件
		if(root==p||root==q||root==null){
			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 right;   // 若找到一个节点  继续向上返回直到根节点
		} else if (left != null && right == null) {
			return left;   // 若找到一个节点  继续向上返回直到根节点
		}else {
			return null;   //没找到结点
		}
    }
}

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

 迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

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

递归

/**
 * Definition for a binary tree node.
 * public 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){
			return null;
		}
		if(root.val>p.val&&root.val>q.val){
			TreeNode left=lowestCommonAncestor1(root.left,p,q);
			if(left!=null){
				return left;
			}
		}
		if(root.val<p.val&&root.val<q.val){
			TreeNode right=lowestCommonAncestor1(root.right,p,q);
			if(right!=null){
				return right;
			}
		}
		return root;
    }
}

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

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 * (思路:其实可以不考虑题目中提示所说的改变树的结构的插入方式。
 * 只要按照二叉搜索树的规则去遍历,遇到空节点就插入节点就可以了。
 */
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //递归终止条件,当遍历到空节点时,就是要插入节点的时候,返回要插入的节点
		if(root==null){
			TreeNode node=new TreeNode(val);
			return node;
		}
		if(root.val<val){
			root.right=insertIntoBST(root.right,val);
		}
		if(root.val>val){
			root.left=insertIntoBST(root.left,val);
		}
		return  root;
    }
}

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

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

  1. 首先找到需要删除的节点;
  2. 如果找到了,删除它。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 * (思路:删除二叉树中节点可以分为以下几种情况:
 * 		1.未找到要删除的节点
 * 		2.找到要删除的节点:
 * 			2.1	删除节点为叶子结点---直接删除
 * 			2.2 删除节点不是叶子结点,但其左孩子为空,右孩子不为空---直接让其父节点指向该节点的右孩子
 * 			2.3	删除节点不是叶子结点,但其右孩子为空,左孩子不为空---直接让其父节点指向该节点的左孩子
 * 			2.4 删除节点不是叶子结点,且左右孩子均不为空:
 * 				右孩子继位,将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上

 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //递归终止条件:遇到空直接返回(没找到要删除的节点
		if(root==null){
			return null;
		}
		//找到要删除的节点:返回删除后的根节点
		if(root.val==key){
			//1.删除节点为叶子结点
			if(root.left==null&&root.right==null){
				return null;
			} else if (root.left!=null&&root.right==null) { //2.删除节点左孩子不为空
				return root.left;
			} else if (root.right != null&&root.left==null) { //3.删除节点右孩子不为空
				return root.right;
			}else{  //4.删除节点左右孩子均不为空
				TreeNode node=root.right;
				while(node.left!=null){
					node=node.left;    //找到右子树的最左边的节点
				}
				node.left=root.left;   //把要删除的节点(root)左子树放在cur的左孩子的位置
				return root.right;
			}
		}
	if(root.val>key){
			root.left=deleteNode(root.left, key);
		}
		if(root.val<key){
			root.right=deleteNode(root.right,key);
		}
		return root;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/86472.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【回味“经典”】DFS练习题解(工作分配问题,最大平台)

这篇文章是一年前写的 走进“深度搜索基础训练“&#xff0c;踏入c算法殿堂&#xff08;四&#xff09;和 走进“深度搜索基础训练“&#xff0c;踏入c算法殿堂&#xff08;二&#xff09;的重编版。 希望以此&#xff0c;唤起对那位故人的回忆。 【搜索与回溯算法】工作分配问…

python之Pandas

1.Pandas简介 Pandas 是 Python 语言的一个扩展程序库&#xff0c;用于数据分析。 Pandas 名字衍生自术语 “panel data”&#xff08;面板数据&#xff09;和 “Python data analysis”&#xff08;Python 数据分析&#xff09;。 Pandas 一个强大的分析结构化数据的工具集…

【数据结构OJ题】相交链表

原题链接&#xff1a;https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2. 思路分析 看到这道题&#xff0c;很容易想到的方法就是暴力求解&#xff0c;就是将一个链表的每个结点的地址…

校园二手物品交易平台/二手交易系统/基于java的校园跳蚤市场系统

​ 摘 要 本文论述了校园二手物品交易平台的设计和实现&#xff0c;该网站从实际运用的角度出发&#xff0c;运用了计算机网站设计、数据库等相关知识&#xff0c;网络和Mysql数据库设计来实现的&#xff0c;网站主要包括用户注册、用户登录、浏览商品、搜索商品、查看商品并进…

【数据结构】顺序队列模拟实现

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

React+Typescript从请求数据到列表渲染

我们在项目src目录下创建一个目录 叫 pages 在里面创建一个组件叫 list.tsx 这里 我启动了自己的java项目 创建接口 你们就也需要弄几个自己的接口做测试 然后 list.tsx 编写代码如下 import * as React from "react";export default class hello extends React.C…

uniapp 回退到指定页面 保存页面状态

uniapp 历史页面回退到指定页面。 getCurrentPages() 内容如下 let delta getCurrentPages().reverse().findIndex(item > item.route "pages/popularScience/daodi") if(delta-1){uni.navigateTo({url: /pages/popularScience/daodi,success: res > {},fa…

Blazor前后端框架Known-V1.2.13

V1.2.13 Known是基于C#和Blazor开发的前后端分离快速开发框架&#xff0c;开箱即用&#xff0c;跨平台&#xff0c;一处代码&#xff0c;多处运行。 Gitee&#xff1a; https://gitee.com/known/KnownGithub&#xff1a;https://github.com/known/Known 概述 基于C#和Blazo…

element+vue 表格行拖拽功能

解决方案 使用 sortable.js 步骤一&#xff1a; 安装 npm install vuedraggable步骤二&#xff1a;引入 import Sortable from sortablejs;步骤三&#xff1a; el-table 添加row-key属性&#xff0c;外层包一层 sortableDiv <div class"sortableDiv"> 拖…

学习开发振弦采集模块的注意事项

学习开发振弦采集模块的注意事项 &#xff08;三河凡科科技/飞讯教学&#xff09;振弦采集模块是一种用来实时采集和处理振弦信号的电子设备&#xff0c;在工业、航空、医疗等领域都有广泛应用。学习开发振弦采集模块需要注意以下几点&#xff1a; 一、硬件选择 首先需要选择…

SpeedBI数据可视化工具:浏览器上做分析

SpeedBI数据分析云是一种在浏览器上进行数据可视化分析的工具&#xff0c;它能够将数据以可视化的形式呈现出来&#xff0c;并支持多种数据源和图表类型。 所有操作&#xff0c;均在浏览器上进行 在浏览器中打开SpeedBI数据分析云官网&#xff0c;点击【免费使用】进入&#…

【C++/C 实现球球大作战】

目录 1.引言2.游戏设计&#xff1a;概述游戏的玩法和操作方式。3.游戏实现&#xff08;1&#xff09;函数 GameInit() 初始化游戏的函数。&#xff08;2&#xff09;函数 GameDraw() 用于绘制游戏场景的函数。&#xff08;3&#xff09;函数 keyControl(int speed) 负责处理键盘…

安装搭建私有仓库Harbor

目录 一、安装docker编排工具docker compose 二、安装Harbor软件包 三、修改配置文件 四、运行安装脚本 五、安装后验证 六、使用Harbor 一、安装docker编排工具docker compose 在github上选择自己想要的版本下载 https://github.com/docker/compose/releases 下载好…

Apache和Nginx各有什么优缺点,应该如何选择?

Apache和Nginx各有什么优缺点&#xff0c;应该如何选择&#xff1f; Apache和Nginx都有各自的优点和缺点&#xff0c;选择应该根据您的具体需求而定。Nginx的优点包括&#xff1a;轻量级&#xff0c;与同等web服务相比&#xff0c;Nginx占用更少的内存和资源&#xff1b;抗并发…

评测凯迪仕K70「千里眼」智能锁:不忘安全初心,便捷体验更上一层

能打败凯迪仕的&#xff0c;只有它自己。这是我们在体验过凯迪仕最新旗舰产品K70「千里眼」智能锁之后的感受。作为凯迪仕2023年最新旗舰机型&#xff0c;K70「千里眼」智能锁在配置上可以说是「机皇」般的存在。3K超高清智能锁猫眼、车规级24GHz雷达、大小双屏设计、三方可视对…

2023网络建设与运维模块三:服务搭建与运维

任务描述: 随着信息技术的快速发展,集团计划2023年把部分业务由原有的X86架构服务器上迁移到ARM架构服务器上,同时根据目前的部分业务需求进行了部分调整和优化。 一、X86架构计算机操作系统安装与管理 1.PC1系统为ubuntu-desktop-amd64系统(已安装,语言为英文),登录用户…

AlphaZero能否从围棋和国际象棋飞跃到量子计算?

一项新的研究表明&#xff0c;DeepMind惊人的游戏算法AlphaZero可以帮助释放量子计算的力量和潜力。 自两年多前出现以来&#xff0c;AlphaZero一再证明了其快速学习能力&#xff0c;将自己提升到围棋&#xff0c;国际象棋和将棋&#xff08;日本象棋&#xff09;的特级大师级别…

【MySQL】视图

目录 一、什么是视图 二、视图的操作 2.1 创建视图 2.2 删除视图 三、视图规则和限制 一、什么是视图 视图是一个虚拟表&#xff0c;其内容由查询定义。同真实的表一样&#xff0c;视图包含一系列带有名称的列和行数据。视图的数据变化会影响到基表&#xff08;创建视图所…

为什么PDF校对工具是2023年数字文档管理的必备良伴

随着企业和个人工作量的日益增长&#xff0c;PDF已成为跨平台文件交换的黄金标准。不仅仅因为它的可靠性&#xff0c;还因为它几乎可以在任何设备上查看。但与此同时&#xff0c;如何确保PDF文档的准确性和专业性呢&#xff1f;答案是使用高效的PDF校对工具。 1.全面性校对&am…

HummingBird 基于 Go 开源超轻量级 IoT 物联网平台

蜂鸟&#xff08;HummingBird&#xff09; 是 Go 语言实现的超轻量级物联网开发平台&#xff0c;包含设备接入、产品管理、物模型、告警中心、规则引擎等丰富功能模块。系统采用GoLang编写&#xff0c;占用内存极低&#xff0c; 单物理机可实现百设备的连接。 在数据存储上&…