当前位置: 首页 > 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…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...