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

二叉树算法的框架套路总结

二叉树算法的框架套路总结

总结

本文主要来源于Leetcode用户:https://leetcode.cn/u/labuladong/,感谢写了这么好的文章作者:labuladong
链接:https://leetcode.cn/problems/same-tree/solutions/6558/xie-shu-suan-fa-de-tao-lu-kuang-jia-by-wei-lai-bu-/

 二叉树的设计总路线:明确一个节点要做什么事情,然后剩下的事情交给框架

void traverse(TreeNode root){// root需要做的事情// 遍历所要做的事情 全部在这里traverse(root.left);traverse(root.right);
}

将所有的节点值加一

void plusOne(TreeNode root){if(root == null){return ;// 首先写出递归结束条件}root.val += 1;plusOne(root.left);plueOne(root.right);
}

如何判断两个二叉树是否相等

/*** 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 boolean isSameTree(TreeNode p, TreeNode q) {// 比较两棵树是否相等// 深度优先遍历// 当两个节点都是null的时候 返回true  递归出口if(p == null && q == null){return true;}else if(p ==null || q == null){return false;}else if(p.val != q.val){return false;}return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}

判断二叉搜索树

  • 下面是错误的代码示例,因为判断一棵树是不是二叉搜索树,需要判断当前节点是不是大于全部的左子树节点以及小于全部的右子树节点,下面的代码只判断了左右节点
boolean isValidBST(TreeNode root) {if (root == null) return true;if (root.left != null && root.val <= root.left.val) return false;if (root.right != null && root.val >= root.right.val) return false;return isValidBST(root.left)&& isValidBST(root.right);
}

正确的代码

boolean isValidBST(TreeNode root) {return isValidBST(root, null, null);
}boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {if (root == null) return true;if (min != null && root.val <= min.val) return false;if (max != null && root.val >= max.val) return false;return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}

二叉搜索树插入一个节点

找到插入位置,然后进行插入操作

TreeNode insertIntoBST(TreeNode root,int val){// 找到空位置插入新节点if(root == null){return new TreeNode(val);}if(root.val < val){root.right = insertIntoBST(root.right,val);}if(root.val > val){root.left = insertIntoBST(root.left,val);}return root;
}

二叉搜索树删除一个节点

首先搭建一个框架

TreeNode deleteNode(TreeNode root,int key){if(root.val == key){// 删除操作}else if(root.val > key){root.left = deleteNode(root.left,key);}else if(root.val < key){root.right = deleteNode(root.right,key);}return root;
}
  • 如果是null 直接return null
if(root.left == null && root.right == null)
{return null;
}
  • 如果当前节点只有一个非空节点,让这个非空节点 代替他
if(root.left == null){return root.right;
}if(root.right == null){return root.left;
}
  • 如果当前节点有两个子节点 找到右子树的最小节点代替自己
if(root.left != null && root.right != null){// 找到右子树的最小节点TreeNode minNode = getMin(root.right);// 将root更换root.val = minNode.val;// 删除minNoderoot.right = deleteNode(root.right,minNode.val);
}
  • 总结代码

TreeNode deleteNode(TreeNode root, int key) {if (root == null) return null;if (root.val == key) {// 这两个 if 把情况 1 和 2 都正确处理了if (root.left == null) return root.right;if (root.right == null) return root.left;// 处理情况 3TreeNode minNode = getMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);} else if (root.val > key) {root.left = deleteNode(root.left, key);} else if (root.val < key) {root.right = deleteNode(root.right, key);}return root;
}TreeNode getMin(TreeNode node) {// BST 最左边的就是最小的while (node.left != null) node = node.left;return node;
} 

相关文章:

二叉树算法的框架套路总结

二叉树算法的框架套路总结 总结 本文主要来源于Leetcode用户&#xff1a;https://leetcode.cn/u/labuladong/&#xff0c;感谢写了这么好的文章作者&#xff1a;labuladong 链接&#xff1a;https://leetcode.cn/problems/same-tree/solutions/6558/xie-shu-suan-fa-de-tao-l…...

【ARM 嵌入式 编译 Makefile 系列 2 - Makefile 如何打印信息】

文章目录 Makefile 打印信息方法介绍Makefile 打印信息方法介绍 在Makefile中,我们可以使用echo命令来打印信息。这种方法适用于大多数的 UNIX shell,包括bash、sh、ksh、zsh等。 在 Makefile 中的规则部分,你可以添加 echo 命令来打印一些信息。例如: all: echo "…...

re学习(34)攻防世界-csaw2013reversing2(修改汇编顺序)

参考文章&#xff1a; re学习笔记&#xff08;27&#xff09;攻防世界-re-csaw2013reversing2_Forgo7ten的博客-CSDN博客攻防世界逆向入门题之csaw2013reversing2_沐一 林的博客-CSDN博客 三种做法 1、ida静态分析修改指令 main函数反编译的代码 由于运行之后的是乱码&…...

centos 7.9 部署django项目

1、部署框架 主要组件&#xff1a;nginx、uwsgi、django项目 访问页面流程&#xff1a;nginx---》uwsgi---》django---》uwsgi---》nginx 2、部署过程 操作系统&#xff1a;centos 7.9 配置信息&#xff1a;4核4G 50G 内网 eip &#xff1a;10.241.103.216 部署过程&…...

12 正则表达式 | HTTP协议相关介绍

文章目录 正则表达式re模块最基础操作&#xff08;匹配开头&#xff09;匹配单个字符匹配多个字符匹配开头结尾匹配分组对于group的理解r的作用re 模块高级用法compilesearchfindall易错点 sub直接替换函数替换 split 根据匹配进行切割字符串&#xff0c;并返回一个列表 python…...

【C语言】数组概述

&#x1f6a9;纸上得来终觉浅&#xff0c; 绝知此事要躬行。 &#x1f31f;主页&#xff1a;June-Frost &#x1f680;专栏&#xff1a;C语言 &#x1f525;该篇将带你了解 一维数组&#xff0c;二维数组等相关知识。 目录&#xff1a; &#x1f4d8;前言&#xff1a;&#x1f…...

8. 实现业务功能--用户注册

目录 1. 顺序图 2. 参数要求 3. 接口规范 4. 创建扩展 Mapper.xml 5. 修改 DAO 6. 创建 Service 接口 7. 实现接口 8. 测试接口 9. 实现 Controller 9.1 密码加密处理 10. 实现前端界面 业务实现过程中主要的包和目录及主要功能&#xff1a; model 包&#xff1a;实体对象 d…...

深入浅出Pytorch函数——torch.nn.init.eye_

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...

版本控制工具Git集成IDEA的学习笔记(第一篇Gitee)

目录 一、Gitee的使用 1、注册网站会员 2、用户中心 3、创建远程仓库 4、配置SSH免密登录 二、集成IDEA&#xff0c;Git项目搭建 1、本地仓库搭建 1&#xff09;创建一个新项目 2&#xff09;打开终端&#xff0c;在当前目录新建一个Git代码库 3&#xff09;忽略文件 …...

【链表】 61. 旋转链表

61. 旋转链表 解题思路 首先计算出链表长度将链表长度进行取余遍历链表 对链表进行分割 得到两个子链表重新连接两个链表比如1 2 3 4 5 k 2 进行分割得到 1 2 3 和 4 5两个子链表 /*** Definition for singly-linked list.* public class ListNode {* int val;* Lis…...

深入浅出Pytorch函数——torch.nn.init.kaiming_uniform_

分类目录&#xff1a;《深入浅出Pytorch函数》总目录 相关文章&#xff1a; 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...

查询Oracle和MySQL数据库中当前所有连接信息

查询Oracle当前所有连接信息&#xff1a; SELECTs.sid AS 会话ID,s.serial# AS 序列号,s.username AS 用户名,s.osuser AS 操作系统用户,s.machine AS 客户端机器,s.program AS 客户端程序,s.status AS 会话状态,s.sql_id AS 正在执行的SQL_ID,t.sql_text AS 正在执行的SQL文本…...

Android glide框架及框架涉及到的设计模式

目录 原文链接Android glide框架 简单使用介绍Glide 框架整体结构设计Glide 框架的优点基本使用&#xff1a;Glide占位符 Android glide框架涉及到的设计模式 原文链接 Android glide框架 简单使用介绍 Glide&#xff1a;快速高效的Android图片加载库&#xff0c;可以自动加载…...

使用yolov5进行安全帽检测填坑指南

参考项目 c​​​​​​​​​​​​​​GitHub - PeterH0323/Smart_Construction: Base on YOLOv5 Head Person Helmet Detection on Construction Sites&#xff0c;基于目标检测工地安全帽和禁入危险区域识别系统&#xff0c;&#x1f680;&#x1f606;附 YOLOv5 训练自己的…...

【BASH】回顾与知识点梳理(三十二)

【BASH】回顾与知识点梳理 三十二 三十二. SELinux 初探32.1 什么是 SELinux当初设计的目标&#xff1a;避免资源的误用传统的文件权限与账号关系&#xff1a;自主式访问控制, DAC以政策规则订定特定进程读取特定文件&#xff1a;委任式访问控制, MAC 32.2 SELinux 的运作模式安…...

vscode远程调试PHP代码

目录 一、准备工作 二、ssh连接和xdebug配置 1.ssh连接 2.xdebug配置 三、xdebug调试&#xff0c;访问 一、准备工作 1.安装vscode里面的两个扩展 2.安装对应PHP版本的xdebug 去xdebug官方&#xff0c;复制自己的phpinfo源码到方框里&#xff0c;再点击Analyse Xdebug: …...

flink1.17 实现 udf scalarFunctoin get_json_object 支持 非标准化json

特色 相比官方的json_value,该函数支持非标准化json,比如v是个object,但是非标准json会外套一层引号,内部有反引号. eg: {"kkkk2": "{\"kkkk1\":\"vvvvvvv\"}" } 支持value为 100L 这种java格式的bigint. {"k":999L…...

基于VUE3+Layui从头搭建通用后台管理系统(前端篇)九:自定义组件封装下

一、本章内容 续上一张,本章实现一些自定义组件的封装,包括文件上传组件封装、级联选择组件封装、富文本组件封装等。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 三、开发视频 基于VUE3+Layui从头搭建通用后台管...

设计模式详解-装饰器模式

类型&#xff1a;结构型模式 实现原理&#xff1a;装饰器模式通过将对象包装在装饰器类中&#xff0c;并在保持类方法签名完整性的前提下&#xff0c;提供额外功能 作用&#xff1a;动态地给一个对象添加一些额外的职责。增加功能方面&#xff0c;装饰器模式比生成子类更灵活…...

Android5:活动生命周期

创建项目Stopwatch activity_main.xml <?xml version"1.0" encoding"utf-8"?> <LinearLayoutxmlns:android"http://schemas.android.com/apk/res/android"xmlns:tools"http://schemas.android.com/tools"android:layout_w…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...