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

【算法刷题 | 二叉树 04】3.27(翻转二叉树、对称二叉树、完全二叉树的节点个数、平衡二叉树、完全二叉树的所有路径)

文章目录

  • 6.翻转二叉树
    • 6.1问题
    • 6.2解法一:递归
      • 6.2.1递归思路
        • (1)确定递归函数的参数和返回值
        • (2)确定终止条件
        • (3)确定单层递归的逻辑
      • 6.2.2全部代码
    • 6.3解法二:层序遍历
  • 7.对称二叉树
    • 7.1问题
    • 7.2解法一:递归
      • 7.2.1递归思路
        • (1)确定递归函数的参数和返回值
        • (2)确定终止条件
        • (3)确定单层递归的逻辑
      • 7.2.2代码实现
    • 7.3解法二:迭代法
  • 8.完全二叉树的节点个数
    • 8.1问题
    • 8.2解法一:递归
    • 8.3解法二:层序遍历
  • 9.平衡二叉树
    • 9.1问题
    • 9.2解法一:递归
      • 9.2.1递归思路
        • (1)确定递归函数返回值和参数值
        • (2)确定终止条件
        • (3)确定递归逻辑
      • 9.2.2代码
  • 10.完全二叉树的所有路径
    • 10.1问题
    • 10.2解法一:前序遍历+回溯
      • 10.2.1递归思路
        • (1)确定递归函数参数以及返回值
        • (2)确定递归终止条件
        • (3)确定递归逻辑
      • 10.2.2代码实现

6.翻转二叉树

6.1问题

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

  • 示例一:

img

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

6.2解法一:递归

6.2.1递归思路

(1)确定递归函数的参数和返回值
  • 题目为翻转根节点的左右孩子
  • 最后返回根节点,即每次递归,传入TreeNode节点,返回该节点
TreeNode reverse(TreeNode node);
(2)确定终止条件
  • 当递归到的该节点为空,即返回
if(node==null){return;
}
(3)确定单层递归的逻辑
  • 当确定该节点不为空,先交换左、右孩子
  • 再分别递归左孩子、右孩子
swap(node);
reverse(node.left);
reverse(node.right);

6.2.2全部代码

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return root;}return reverse(root);}private TreeNode reverse(TreeNode node){if(node==null){return node;}swap(node);reverse(node.left);reverse(node.right);return node;}private void swap(TreeNode node){TreeNode tmp=node.left;node.left=node.right;node.right=tmp;}
}

6.3解法二:层序遍历

  1. 将每一个从队列取出来的元素,进行左孩子和有孩子的交换
class Solution {public TreeNode invertTree(TreeNode root) {//广度优先遍历Queue<TreeNode> queue=new LinkedList<>();if(root==null){return root;}queue.offer(root);while(!queue.isEmpty()){int size=queue.size();while(size>0){TreeNode node=queue.poll();swap(node);if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}size--;}}return root;}private void swap(TreeNode node){TreeNode tmp=node.left;node.left=node.right;node.right=tmp;}
}

7.对称二叉树

7.1问题

给你一个二叉树的根节点 root , 检查它是否轴对称。

  • 示例一:

img

输入:root = [1,2,2,3,4,4,3]
输出:true

7.2解法一:递归

7.2.1递归思路

(1)确定递归函数的参数和返回值
  1. 比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的是两个树,参数自然也是左子树节点和右子树节点
  2. 返回值为boolean类型
boolean compare(TreeNode left,TreeNode right)
(2)确定终止条件
  1. 首先排除左孩子、右孩子节点有空的情况
    • 左孩子为空,右孩子不为空:return false
    • 左孩子不为空,右孩子为空:return false
    • 左、右孩子均为空:return true
  2. 左、右孩子均不为空:
    • 比较左右孩子的数值,不相同:return false
if (left == NULL && right != NULL) return false;
else if (left != NULL && right == NULL) return false;
else if (left == NULL && right == NULL) return true;
else if (left->val != right->val) return false; // 注意这里我没有使用else
(3)确定单层递归的逻辑
  • 单层递归的逻辑就是处理左右节点都不为空,且数值相同的情况。
    • 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
    • 比较内侧是否对称,传入左节点的右孩子,右节点的左孩子。
    • 如果左右都对称就返回true ,有一侧不对称就返回false 。
boolean outside = compare(left.left, right.right);   // 左子树:左、 右子树:右
boolean inside = compare(left.right, right.left);    // 左子树:右、 右子树:左
boolean isSame = outside && inside;                    // 左子树:中、 右子树:中(逻辑处理)
return isSame;

7.2.2代码实现

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null){return true;}return compare(root.left,root.right);}private boolean compare(TreeNode left,TreeNode right){if(left==null && right!=null){return false;}else if(left!=null && right==null){return false;}else if(left==null && right==null){return true;}else if(left.val!=right.val){return false;}//单层递归逻辑boolean out=compare(left.left,right.right);boolean in=compare(left.right,right.left);return (out&&in);}
}

7.3解法二:迭代法

  1. 使用队列来比较两个树(根节点的左右子树)是否相互翻转,(注意这不是层序遍历

101.对称二叉树

class Solution {public boolean isSymmetric(TreeNode root) {//迭代法if(root==null){return true;}Queue<TreeNode> queue=new LinkedList<>();//添加根节点的左右孩子queue.offer(root.left);queue.offer(root.right);while(!queue.isEmpty()){TreeNode left=queue.poll();TreeNode right=queue.poll();//1、判断两个节点是否均为空if(left==null && right==null){continue;   //对称,结束此次循环,再次取出新的两个节点判断}//2、判断不符合对称条件if(left==null || right==null || (left.val!=right.val)){return false;}//3、添加新的两个节点:外层+内层queue.offer(left.left);queue.offer(right.right);queue.offer(left.right);queue.offer(right.left);}return true;}}

8.完全二叉树的节点个数

8.1问题

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

  • 示例一:

img

输入:root = [1,2,3,4,5,6]
输出:6

8.2解法一:递归

class Solution {public int countNodes(TreeNode root) {return count(root);}private int count(TreeNode node){if(node==null){return 0;}int leftCount=count(node.left);int rightCount=count(node.right);return leftCount+rightCount+1;}
}

8.3解法二:层序遍历

class Solution {public int countNodes(TreeNode root) {//广度优先遍历Queue<TreeNode> queue=new LinkedList<>();int count=0;if(root==null){return count;}queue.offer(root);while(!queue.isEmpty()){int size=queue.size();count+=size;while(size>0){TreeNode node=queue.poll();if(node.left!=null){queue.offer(node.left);}if(node.right!=null){queue.offer(node.right);}size--;}}return count;}}

9.平衡二叉树

9.1问题

给定一个二叉树,判断它是否是 平衡二叉树

  • 示例一:

img

输入:root = [3,9,20,null,null,15,7]
输出:true

9.2解法一:递归

9.2.1递归思路

(1)确定递归函数返回值和参数值
  1. 题目为确定一棵树是否为平衡树
  2. 平衡树的定义:一棵树为空或者其左右节点的高度差的绝对值不超过1
  3. 即递归函数参数为一个树节点,返回值为该节点的高度(注意:若返回-1,则表明该树不平衡)
int isBalancedTree(TreeNode node)
(2)确定终止条件
  1. 若该节点为null,返回0
if(node==null){return 0;
}
(3)确定递归逻辑
  1. 传入一个节点,要求返回其高度,即需要求其左、右节点的高度
  2. 分别求完左、右节点的高度之后,判断其中是否为-1,若为-1,则返回-1,代表不平衡
  3. 若均不为-1,则求出该节点的平衡因子,若其绝对值超过1,则返回-1,代表不平衡
  4. 否则返回当前节点为根节点的树的最大高度
int leftHeight=isBalancedTree(node.left);
int rightHeight=isBalancedTree(node.right);
if(leftHeight==-1 || rightHeight==-1){return -1;
}
if(Math.abs(leftHeight-rightHeight)>1){return -1;
}
return 1+Math(leftHeight,rightHeight);

9.2.2代码

class Solution {public boolean isBalanced(TreeNode root) {return isBalancedTree(root)!=-1;}private int isBalancedTree(TreeNode node){if(node==null){return 0;}int leftHeight=isBalancedTree(node.left);int rightHeight=isBalancedTree(node.right);if(leftHeight==-1 || rightHeight==-1){return -1;}if(Math.abs(leftHeight-rightHeight)>1){return -1;}return 1+Math.max(leftHeight,rightHeight);}
}

10.完全二叉树的所有路径

10.1问题

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

  • 示例一:

img

输入:root = [1,2,3,null,5]
输出:["1->2->5","1->3"]

10.2解法一:前序遍历+回溯

  1. 题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径
  2. 把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

image-20240327153241191

10.2.1递归思路

(1)确定递归函数参数以及返回值
  1. 求以node为根节点到达叶子节点的路径
  2. paths存放路径值
  3. res存放最终结果
void traversal(TreeNode node,List<Integer> paths,List<String> res)
(2)确定递归终止条件
  1. 当遍历到了叶子节点,即为一条完整的路径
  2. 取出paths的全部节点,并加入到res中
  3. 直接return
if(node.left==null && node.right==null){// 输出StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串,速度更快for (int i = 0; i < paths.size() - 1; i++) {sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;
}
(3)确定递归逻辑
 		// 递归和回溯是同时进行,所以要放在同一个花括号里if (root.left != null) { // 左traversal(root.left, paths, res);paths.remove(paths.size() - 1);// 回溯}if (root.right != null) { // 右traversal(root.right, paths, res);paths.remove(paths.size() - 1);// 回溯}

10.2.2代码实现

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<Integer> paths=new ArrayList<>();List<String> res=new ArrayList<>();traversal(root,paths,res);return res;}private void traversal(TreeNode node,List<Integer> paths,List<String> res){//1、前序遍历(中左右)处理该节点paths.add(node.val);//2、终止条件:该节点为叶子节点if(node.left==null && node.right==null){StringBuilder sb=new StringBuilder();for(int i=0;i<paths.size()-1;i++){sb.append(paths.get(i)).append("->");}//加入最后一个节点sb.append(paths.get(paths.size()-1));res.add(sb.toString());return;}//3、递归逻辑+回溯if(node.left!=null){traversal(node.left,paths,res);//回溯paths.remove(paths.size() - 1); //去除最后一个节点}if(node.right!=null){traversal(node.right,paths,res);//回溯paths.remove(paths.size() - 1); //去除最后一个节点}}
}

相关文章:

【算法刷题 | 二叉树 04】3.27(翻转二叉树、对称二叉树、完全二叉树的节点个数、平衡二叉树、完全二叉树的所有路径)

文章目录 6.翻转二叉树6.1问题6.2解法一&#xff1a;递归6.2.1递归思路&#xff08;1&#xff09;确定递归函数的参数和返回值&#xff08;2&#xff09;确定终止条件&#xff08;3&#xff09;确定单层递归的逻辑 6.2.2全部代码 6.3解法二&#xff1a;层序遍历 7.对称二叉树7.…...

【uniapp】uniapp实现免密登录

文章目录 一、概要二、整体架构流程三、技术名词解释四 、技术细节1.存取token有效期&#xff1f;2.使用setStorageSync而不使用setStorage&#xff1f;3.使用onLaunch而不使用全局路由&#xff1f; 一、概要 打开一个网页或小程序的时候&#xff0c;我们有时候会自动进入主页…...

2024-03-27 问AI: 介绍一下深度学习中的 Darknet

文心一言 在深度学习中&#xff0c;Darknet是一个开源的神经网络框架&#xff0c;由Joseph Redmon开发&#xff0c;主要用于实现深度学习算法。它以其高效的实现和速度受到广泛关注&#xff0c;并在许多计算机视觉竞赛中取得了优异的结果。 Darknet的特点包括&#xff1a; 轻…...

POJ3037 + HDU-6714

两道最短路好题 POJ3037 手玩一下 发现每一点的速度可以直接搞出来&#xff0c;就是pow(2,h[1][1]-h[i][j])*V 那么从这个点出发到达别的点的耗费的时间都是上面这个数的倒数&#xff0c;然后直接跑最短路就好了 #include<iostream> #include<vector> #include<…...

Ubuntu搭建环境Cmake-Libtorch-Torchvision-PCL-VTK-OpenCV

Ubuntu搭建环境Cmake-Libtorch-Torchvision-PCL-VTK-OpenCV 安装Cmake安装libtorch安装torchvision安装PCL安装VTK安装OpenCV设置环境变量 仅供本人记录查阅使用 安装Cmake Cmake下载地址 解压 进入目录会看到只有 bin doc man share三个文件夹&#xff0c;没有 bootstrap文…...

分享多种mfc100u.dll丢失的解决方法(一键修复DLL丢失的方法)

在使用电脑过程中&#xff0c;我们经常会遇到一些陌生的DLL文件&#xff0c;例如mfc100u.dll。这些DLL文件是动态链接库&#xff08;Dynamic Link Libraries&#xff09;的缩写&#xff0c;它们包含了可以被多个程序共享的代码和数据。今天&#xff0c;我们将深入探讨mfc100u.d…...

Redis是单线程还是多线程?(面试题)

1、Redis5及之前是单线程版本 2、Redis6开始引入多线程版本&#xff08;实际上是 单线程多线程 版本&#xff09; Redis6及之前版本&#xff08;单线程&#xff09; Redis5及之前的版本使用的是 单线程&#xff0c;也就是说只有一个 worker队列&#xff0c;所有的读写操作都要…...

动态菜单设计

需求&#xff1a; 登录不同用户 显示不同的菜单 思路&#xff1a;根据用户id 左关联表 查询出对应的菜单选项 查询SQL select distinct-- 菜单表 去除重复记录sys_menu.id,sys_menu.parentId, sys_menu.name from -- 权限表sys_menu-- 角色与权限表 菜单表id 角色菜…...

Haproxy负载均衡介绍即部署

haproxy的原理&#xff1a; 提供高可用、负载均衡以及基于TCP&#xff08;四层&#xff09;和HTTP&#xff08;七层&#xff09;应用的代理&#xff0c;支持虚拟主机&#xff0c;开源可靠的一款软件。 适用于哪些负载特别大的web站点&#xff0c;这些站点通常又需要回话保持和七…...

基于大语言模型的云故障根因分析|顶会EuroSys24论文

*马明华 微软主管研究员 2021年CCF国际AIOps挑战赛程序委员会主席&#xff08;第四届&#xff09; 2021年博士毕业于清华大学&#xff0c;2020年在佐治亚理工学院做访问学者。主要研究方向是智能运维&#xff08;AIOps&#xff09;、软件可靠性。近年来在ICSE、FSE、ATC、EuroS…...

Windows直接运行python程序

Windows直接运行python程序 一、新建bat脚本二、新建vbs脚本 一、新建bat脚本 新建bat批处理脚本&#xff0c;写入以下内容 echo off call conda activate pytorch python app.pyecho off&#xff1a;在此语句后所有运行的命令都不显示命令行本身&#xff0c;但是本身的指令是…...

经典应用丨光伏行业扫码追溯新标杆,海康机器人AI智能读码器!

去年&#xff0c;光伏发电行业持续高速发展&#xff0c;我国仅在前九个月累计装机521.08GW&#xff0c;同比增长达到45.3%&#xff0c;已成为第二大电源类型超过水电。根据《2023中国与全球光伏发展白皮书》预测&#xff0c;到2030年&#xff0c;中国能够实现国家规划的风电和光…...

逆流而上的选择-积极生活,逆流而上

首先请大家看一个故事 李明坐在公司的开放式办公区&#xff0c;耳边是键盘敲击声的交响乐&#xff0c;眼前是一行行跳跃的代码。他的眼神有些恍惚&#xff0c;显示器的蓝光在他眼镜上反射出时代的光芒&#xff0c;这光芒既耀眼又刺眼。他即将35岁&#xff0c;在这个年纪&#x…...

SpringMVC基础Controller

文章目录 Controller 的编写和配置1. Controller 注解类型2. RequestMapping 注解类型3. 编写请求方法4. 请求参数和路径变量 Controller 的编写和配置 Controller 注解和 RequestMapping 注解是 Spring MVC 最重要的两个注解。 使用基于注解的控制器的优点如下&#xff1a; …...

spark 参数

spark.yarn.executor.memoryOverhead 默认值是384M Configuration - Spark 3.5.1 Documentation...

java调用jacob进行文件转换ppt转pdf或者png

java调用jacob进行文件转换ppt转pdf或者png 前情提要 最近项目上&#xff0c;遇到一个复杂的ppt&#xff0c;最终要求是要将ppt每一页转成图片原本这个是不难&#xff0c;网上一搜一大堆案例&#xff0c;外加我本身也比较精通aspose&#xff0c;那还不是分分钟搞定。结果就是…...

鸿蒙HarmonyOS应用开发之使用DevEco Studio模板构建NDK工程

NDK通过CMake和Ninja编译应用的C/C代码&#xff0c;编译过程如下图所示。 核心编译过程如下&#xff1a; 根据CMake配置脚本以及build-profile.json5中配置的externalNativeOptions构建参数&#xff0c;与缓存中的配置比对后&#xff0c;生成CMake命令并执行CMake。 执行Ninja…...

uniapp流浪动物救助小程序Java宠物领养小程序springboot

uniapp流浪动物救助小程序Java宠物领养小程序springboot 代码40块&#xff0c;需要的私聊 前台基于uniapp小程序 后台管理基于springbootvue前后端分离项目 开发语言&#xff1a;Java 框架&#xff1a;springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xf…...

工程企业的未来选择:Java版工程项目管理系统平台与数字化管理的融合

在现代化的工程项目管理中&#xff0c;一套功能全面、操作便捷的系统至关重要。本文将介绍一个基于Spring Cloud和Spring Boot技术的Java版工程项目管理系统&#xff0c;结合Vue和ElementUI实现前后端分离。该系统涵盖了项目管理、合同管理、预警管理、竣工管理、质量管理等多个…...

Vue使用el-statistic和el-card显示大屏中的统计数据

​ 一、页面内容&#xff1a; <el-row :gutter"20"><el-col :span"6"><el-card class"box-card"><div><el-statisticgroup-separator",":precision"2":value"value2":title"tit…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...