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

二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏):

抓紧刷题巩固一下了

目录

1.单值二叉树

题目描述

思路1

代码1

思路2

 代码2

2.相同的树

题目描述 

思路

代码

3.二叉树的前序遍历

代码

 思路


1.单值二叉树

965. 单值二叉树 - 力扣(LeetCode)

题目描述

思路1

利用递归:

首先检查根与左右节点的值是否相等,如果不相等就能直接返回false ,都一样就依次进入左右子树开始检查子树。

对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。如果左右子树都满足条件,则继续递归地检查左子树和右子树

递归的终止条件是当遍历到叶子节点时,此时返回 true

代码1

bool isUnivalTree(struct TreeNode* root) {if(root==NULL)return true;if(root->left!=NULL&&root->left->val!=root->val){return false;}if(root->right!=NULL&&root->right->val!=root->val){return false;}return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

思路2

首先检查根节点是否为空,如果为空则直接返回 true

然后,代码会递归地检查左子树和右子树。对于每个节点,它会检查其左子节点和右子节点的值是否与当前节点的值相同,如果不同则返回 false。同时,它也会递归地检查左子树和右子树是否为unival树(一旦不满足条件,直接返回false)

满足了就走到最后,返回true

 代码2

bool isUnivalTree(struct TreeNode* root) {if(root==NULL)//看根{return true;}if(root->left)//左子树不为空就先看左子树符合否{if(root->left->val!=root->val||!isUnivalTree(root->left))return false;}if(root->right)//右子树不为空{if(root->right->val!=root->val||!isUnivalTree(root->right))return false;}return true;
}

2.相同的树

100. 相同的树 - 力扣(LeetCode)

题目描述 

思路

先根和根比,比完再比左子树和右子树

1. 两者都是空时也相等

2. 左节点或右节点一个存在一个不存在返回false;都存在不相等也是false

3.开始递归,都是NULL时返回true或者返回false停止

代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL){return true;}if(p==NULL&&q!=NULL){return false;}if(q==NULL&&p!=NULL){return false;}if(p->val!=q->val){return false;}bool left= isSameTree(p->left,q->left);bool right= isSameTree(p->right,q->right);return left&&right;
}


3.二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

代码

int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : 1 + TreeSize(root->left) + TreeSize(root->right);
}void preorder(struct TreeNode* root, int* a, int* i)
{if (root == NULL){return;}a[*i] = root->val;(*i)++;preorder(root->left, a, i);preorder(root->right, a, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {int n = TreeSize(root);*returnSize=n;int* a=(int*)malloc(sizeof(int)*n);int i=0;preorder(root,a,&i);return a;
}

 思路

1.首先题目要求放到malloced的数组里,那就要考虑大小的问题,最后还是运用TreeSize来求一下树里元素的数量比较好,求出来后直接赋值给*returnsize

2.一般使用递归,但是我们已经在函数里面动态开辟了,递归每次调用会消耗很多,最好的办法还是在构建一个函数来进行前置遍历和放入的操作。

3.考虑到参数设置问题,root要有,数组a也要有。那想到需要一个下标才能确保递归时正确放到位置,这个下标还不能在递归函数里面定义,那样没用(都是新的,独立的变量)。

所以要作为参数传入的同时还能保证递归时改变的都是同一个变量那就有两种方法:

  • 全局变量
  • 传入地址:地址虽然也是临时拷贝,但是都是指向同一块区域

相关文章:

二叉树基础oj练习(单值二叉树、相同的树、二叉树的前序遍历)

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏): 抓紧刷题巩固一下了 目录 1.单值二叉树 题目描述 思路1 代码1 思路2 代码2 2.相同的树 题目描述 思路 代码 3.二叉树的前序遍历 代码 思路 1.单值二叉树 965. 单值二叉树 - 力扣(LeetCod…...

自动化创建ETX用户帐号

在芯片设计行业,ETX是常见的远程访问环境。用户在通过ETX访问远程环境前必须首先加入ETX系统,然后通过profile分配相关的环境的访问权限。 通常这些操作在ETX WEB页面手工操作,如果我们期望实现用户帐号注册全自动化,就需要将以上…...

Android 实现集合去重的方法

方法一&#xff1a;使用HashSet 将集合转换为HashSet。 Set<String> set new HashSet<>(list);将HashSet转换回List。 List<String> uniqueList new ArrayList<>(set);方法二&#xff1a;使用Java 8的Stream API 将列表转换为Stream。 Stream&l…...

【Vue3】2-12 : 【案例】搜索关键词加筛选条件的综合

本书目录&#xff1a;点击进入 一、【案例】搜索关键词加筛选条件的综合 1.1、逻辑 1.2、效果 1.3、json数据 - 02-data.json 1.4、代码 一、【案例】搜索关键词加筛选条件的综合 1.1、逻辑 计算属性 - 绑定list&#xff0c;并过滤 input 双向绑定 - 当input改变时&…...

unity小程序websocket:nginx配置https (wss)转http (ws)及其他问题解决

目录 前言 实际运用场景 处理流程如下 nginx配置ssl和wss 配置过程中遇到的问题 1、无法连接服务器 2、通过IP可以访问&#xff0c;域名却不行 问题描述 解决 3、如何判断该域名是否备案了 前言 为了服务器网络的通用性&#xff0c;我们在实现移动端的游戏转微信小程序…...

MySql数据库对接Orcal数据库,需要考虑的前提问题

1.主表 从表的表关系&#xff1b;主键id 的关联问题&#xff1b; 2.字段类型的一致性问题&#xff08;备注&#xff1a;像varchar类型的一点要谨防数据过长抛错&#xff09;&#xff1b; 3.实体类字段两表一致性问题&#xff1b; 4.入表不为空问题&#xff0c;判空尽量在实体…...

K8S的存储卷---数据卷

容器内的目录和宿主机的目录进行挂载 容器在系统上的生命周期是短暂的。delete&#xff0c;K8S用控制器创建的pod&#xff0c;delete相当于重启&#xff0c;容器的状态也会恢复到初始状态。一旦回到初始状态&#xff0c;所有的后天编辑的文件都会消失 容器和节点之间创建一个…...

【量化交易故事】小明开启了量化创业之旅-01

故事开始于2023年的春天&#xff0c;小明是一位对金融市场充满热情的IT工程师。在经历了数次基于主观判断和个人情绪进行投资却收获平平后&#xff0c;他意识到传统交易方式中的人为因素难以避免&#xff0c;而这往往成为影响投资决策稳定性和准确性的关键障碍。在一次偶然的机…...

ffmpeg写YUV420文件碰到阶梯型横线或者条纹状画面的原因和解决办法

版权声明&#xff1a;本文为CSDN博主「文三~」的原创文章&#xff0c;遵循CC 4.0 BY-SA版权协议&#xff0c;转载请附上原文出处链接及本声明。 原文链接&#xff1a;https://blog.csdn.net/asdasfdgdhh/article/details/112831581 看到了&#xff0c;转载&#xff0c;留着备份…...

案例:新闻数据加载

文章目录 介绍相关概念相关权限约束与限制完整示例 代码结构解读构建主界面数据请求下拉刷新总结 介绍 本篇Codelab是基于ArkTS的声明式开发范式实现的样例&#xff0c;主要介绍了数据请求和touch事件的使用。包含以下功能&#xff1a; 数据请求。列表下拉刷新。列表上拉加载…...

数学的雨伞下:理解世界的乐趣

这本书没有一个公式&#xff0c;却讲透了数学的本质&#xff01; 《数学的雨伞下&#xff1a;理解世界的乐趣》。一本足以刷新观念的好书&#xff0c;从超市到对数再到相对论&#xff0c;娓娓道来。对于思维空间也给出了一个更容易理解的角度。 作者&#xff1a;米卡埃尔•洛奈…...

补充 vue3用户管理权限(路由控制)

之前有人问我 &#xff0c;如果是二级路由如何添加&#xff0c;这里我做一个补充吧。直接拿方法去用就行。也不做解释了。稍微看下就能看懂了 假设&#xff0c;后端返回给我们一个数据 [“/defa”,"/defa/defa1"] 这样的一个路由表&#xff0c;我们就需要通过这个路…...

C++ 深度优先搜索DFS || 模版题:排列数字

给定一个整数 n &#xff0c;将数字 1∼n 排成一排&#xff0c;将会有很多种排列方法。 现在&#xff0c;请你按照字典序将所有的排列方法输出。 输入格式 共一行&#xff0c;包含一个整数 n 。 输出格式 按字典序输出所有排列方案&#xff0c;每个方案占一行。 数据范围 1…...

计算机找不到msvcp120.dll如何解决?总结五个可靠的教程

在计算机使用过程中&#xff0c;遇到“找不到msvcp120.dll”这一问题常常令人困扰。msvcp120.dll作为Windows系统中至关重要的动态链接库文件&#xff0c;对于许多应用程序的正常运行起着不可或缺的作用。那么&#xff0c;究竟是什么原因导致找不到msvcp120.dll呢&#xff1f;又…...

法线变换矩阵的推导

背景 在冯氏光照模型中&#xff0c;其中的漫反射项需要我们对法向量和光线做点乘计算。 从顶点着色器中读入的法向量数据处于模型空间&#xff0c;我们需要将法向量转换到世界空间&#xff0c;然后在世界空间中让法向量和光线做运算。这里便有一个问题&#xff0c;如何将法线…...

React.Children.map 和 js 的 map 有什么区别?

JavaScript 中的 map 不会对为 null 或者 undefined 的数据进行处理&#xff0c;而 React.Children.map 中的 map 可以处理 React.Children 为 null 或者 undefined 的情况。 React 空节点&#xff1a;可以由null、undefined、false、true创建 import React from reactexport …...

13.Kubernetes部署Go应用完整流程:从Dockerfile到Ingress发布完整流程

本文以一个简单的Go应用Demo来演示Kubernetes应用部署的完整流程 1、Dockerfile多阶段构建 Dockerfile多阶段构建 [root@docker github]# git clone https://gitee.com/yxydde/http-dump.git [root@docker github]# cd http-dump/ [root@docker http-dump]# cat Dockerfile …...

叉车车载终端定制_基于MT6762安卓核心板的车载终端设备方案

叉车车载终端是一款专为叉车车载场景设计的4英寸Android车载平板电脑。它采用了高能低耗的8核ARM架构处理器和交互开放的Android 12操作系统&#xff0c;算力表现强大。此外&#xff0c;该产品还具备丰富的Wi-Fi-5、4G LTE和蓝牙等通讯功能&#xff0c;可选配外部车载蘑菇天线&…...

【CSS】保持元素宽高比

保持元素的宽高比&#xff0c;在视频或图片展示类页面是一个重要功能。 本文介绍其常规的实现方法。 实现效果 当浏览器视口发生变化时&#xff0c;元素的尺寸随之变化&#xff0c;且宽高比不变。 代码实现 我们用最简单的元素结构来演示&#xff0c;实现宽高比为4&#xf…...

使用 Docker 和 Diffusers 快速上手 Stable Video Diffusion 图生视频大模型

本篇文章聊聊&#xff0c;如何快速上手 Stable Video Diffusion (SVD) 图生视频大模型。 写在前面 月底计划在机器之心的“AI技术论坛”做关于使用开源模型 “Stable Diffusion 模型” 做有趣视频的实战分享。 因为会议分享时间有限&#xff0c;和之前一样&#xff0c;比较简…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

Docker 本地安装 mysql 数据库

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

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...