二叉树+树的OJ题讲解

求第K层节点个数

思路:走到K==1就不走了,一次传回得到的值在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
//树的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//手搓一棵树 malloc
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//怎么指向根据树写出来node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}//求第K层节点个数
int TreeLevelSize(BTNode* root, int k)
{if (root == NULL)return NULL;if (k == 1)return 1;//到K==1层就返回程序return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1);//其实一遍一遍的递归也算是--K了
}
int main()
{BTNode* root = CreatBinaryTree();printf("%d", TreeLevelSize(root,3));return 0;
}

二叉树查找值为X的节点

根据提示自己写的

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;//该函数有返回值类型,是空也要返回空,不能直接写逗号if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);BTNode* ret2 = TreeFind(root->right, x);if (root->left == x)return ret1;if (root->right == x)return ret2;return NULL;//根左右都没有,返回空
}
int main()
{BTNode* root = CreatBinaryTree();TreeFind(root,4);return 0;
}

根本运行不出来

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root->data == x)return root;BTNode* ret1 =NULL;BTNode* ret2 = NULL;if (root->left == x){ret1 = root->left;return ret1;}if (root->right == x){ret2 = root->right;return ret2;}return NULL;//这样应该每个情况都有返回值
}int main()
{BTNode* root = CreatBinaryTree();TreeFind(root,4);return 0;
}

第二种也是错的
在这里插入图片描述
判断条件值的类型是不对应的

查找的正确写法

BTNode* TreeFind(BTNode* root, BTDataType x)
{/*首先每一种状态必须要有返回值必须要有变量接收递归的值判断条件只要ret1 ret2不为空那就说明有与x相等的,直接判断ret就行就不会涉及root->left与x比较,而是root->data与x比较*/if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);BTNode* ret2 = TreeFind(root->right, x);if (ret1)return ret1;//左子树有就不用再看右子树了,直接返回if (ret2)return ret2;return NULL;//左右都没有
}

leetcode 100.相同的树(简单)

在这里插入图片描述

思路:根和根比较,左子树和左子树比,右子树和右子树比

比较相同,一个相同没用,必须全部相同,返回什么?太难写了
反过来写:把所有的不相等的情况写出来返回false 走到光标闪动的位置就是全都相等

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL)return true;if(p==NULL||q==NULL)return false;//他俩都有值//先比根吧,在递归左子树右子树if(p->val!=q->val)return false;return isSameTree(p->left,q->left)&& isSameTree(p->right,q->right);//都不返回错误//那就是相同的树了return true;
}

nice哦,逻辑能梳理清楚了

leetcode 101. 对称二叉树(和第一题类似)

在这里插入图片描述
思路:根和根比,左子树和右子树比,右子树和左子树比

错误写法:

bool _isSymmetric(struct TreeNode*left, struct TreeNode*right)
{//用来判断不等吧,相等返回值不好写if(left==NULL&&right==NULL)return true;if(left==NULL||right==NULL)return false;//都有值了,判断值if(left!=right)return false;return _isSymmetric(left,right)&& _isSymmetric(right,left);//左右 右左都要比return true;
}
bool isSymmetric(struct TreeNode* root) 
{return _isSymmetric(root->left,root->right);}

在这里插入图片描述
这个测试用例过不了
在这里插入图片描述

是因为我只是传了左右节点而不是左右子树
到了节点2,我比较的是3,4 而不是3 和 3 还是要传根节点的左右子树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
//再写一个函数 一般在前面+横杠
bool _isSymmetric(struct TreeNode*p, struct TreeNode*q)
{//用来判断不等吧,相等返回值不好写if(p==NULL&&q==NULL)return true;if(p==NULL||q==NULL)return false;if(p->val!=q->val)return false;return _isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);return true;/*if(p->right==NULL||q->left==NULL)return false;//都有值了,判断值if(p->left!=q->right||p->right!=q->left)return false;return _isSymmetric(p->left,q->right)&& _isSymmetric(p->right,q->left);//左右 右左都要比return true;*/
//}
bool isSymmetric(struct TreeNode* root) 
{return _isSymmetric(root->left,root->right);}

思路得清晰,判断完值之后后面就是重复的判断子树,直接递归了,不要做多余的判断,后面的操作相同

144.二叉树的前序遍历并存到数组里(数组自己malloc出来)

我们该扩容多大的数组?—>把树遍历一遍求个数

在这里插入图片描述

 int TreeSize(struct TreeNode*root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;//左子树节点个数+右子树节点个数+根}void preorder(struct TreeNode*root,int*a,int *pi){if(root==NULL)return;a[(*pi)++]=root->val;preorder(root->left,a,pi);preorder(root->right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*(*returnSize));int i=0;preorder(root,a,&i);return a;
}

其中returnsize是第一次接触的输出型参数

力扣中要返回数组就是要返回数组大小

为什么不传i而是传指针pi

因为i在形参是局部变量是并没有因为递归而累加(实际改变的)所以要改成传址调用

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Android kotlin之配置kapt编译器插件

配置项目目录下的gradle/libs.versions.toml文件&#xff0c;添加kapt配置项&#xff1a; 在模块目录下build.gradle.kt中增加 plugins {alias(libs.plugins.android.application)alias(libs.plugins.jetbrains.kotlin.android)// 增加该行alias(libs.plugins.jetbrains.kotl…

类和对象——拷贝构造函数,赋值运算符重载(C++)

1.拷⻉构造函数 如果⼀个构造函数的第⼀个参数是自身类类型的引用&#xff0c;且任何额外的参数都有默认值&#xff0c;则此构造函数也叫做拷贝构造函数&#xff0c;也就是说拷贝构造是⼀个特殊的构造函数。 // 拷贝构造函数//d2(d1) Date(const Date& d) {_year d._yea…

STM32G4的数模转换器(DAC)功能介绍

目录 概述 1 DAC介绍 1.1 功能 1.2 主要特征 1.3 DAC特性总结 ​2 DAC模块框架结构 3 DAC数据格式 3.1 单DAC通道 3.2 双通道数据格式 3.3 有符号、无符号数据 4 DAC数据转换 ​5 DAC输出电压 概述 本文主要介绍STM32G4的数模转换器&#xff08;DAC&#xff09;功能&a…

Pointnet++改进68:添加FFCM |融合傅里叶卷积

简介:1.该教程提供大量的首发改进的方式,降低上手难度,多种结构改进,助力寻找创新点!2.本篇文章对Pointnet++特征提取模块进行改进,加入,提升性能。3.专栏持续更新,紧随最新的研究内容。 目录 1.理论介绍 2.修改步骤 2.1 步骤一 2.2 步骤二 2.3 步骤三 1.理论介绍 …

Linux:解决远程X无法连通问题,X-Server开启TCP连接

一、问题分析 提前申明&#xff1a; 本次实验使用REHL 8 进行操作&#xff01; 客户机 A 为X-Client &#xff0c;即远程X的客户端。 服务机 B 为X-Server&#xff0c;即远程X的服务端。 问题的所有操作均在已经配置好Xorg的前提下进行的&#xff0c;不知道不配置会有什么影响&…

零基础Java第十九期:认识String(一)

目录 一、String的重要性 二、String的常用方法 2.1. 字符串构造 2.2. String对象的比较 2.3. 字符串查找 2.4. 转化 2.4. 字符串替换 2.5. 字符串拆分 2.6. 字符串截取 一、String的重要性 在C语言中已经涉及到字符串了&#xff0c;但是在C语言中要表示字符串只能…

HarmonyOS4+NEXT星河版入门与项目实战--------ArkTs语言与TypeScript语法

文章目录 1、ArkTs语言1、ArkTs 特点2、ArkTs与Javascript关系 2、TypeScript 语法 1、ArkTs语言 在html的开发中&#xff0c;实现一个页面元素&#xff0c;比如Button&#xff0c;往往包含了以下三种要素&#xff1a;JS、HTML、CSS。JS处理逻辑与响应、HTML 用来声明标签生成…

使用yak编写yakit漏洞检测插件

前言 在使用yakit进行编写yaml插件的时候遇到了yaml无法处理的情况&#xff0c;我不知道是不是yaml无法处理或者说是yakit和yaml的兼容还不够&#xff0c;面对变量的处理还是有些难受&#xff0c;于是花了点时间看了官网的yak语法的手册和其他人写的yak插件尝试使用yak语言来完…

信也科技和云杉网络的AI可观测性实践分享

1. 信也科技 2、云杉网络 2.1 中国移动

Blossom:开源私有部署的markdown笔记软件

在信息化、数字化时代&#xff0c;我们每个人的生活和工作都离不开笔记和知识管理。从简单的待办事项&#xff0c;到复杂的项目计划&#xff0c;再到存储大量个人知识的工具&#xff0c;如何选择一个高效、便捷且符合个人需求的笔记软件&#xff0c;成了许多人的难题。最近在逛…

Spring:DI依赖注入的方式

Spring为我们提供了两种注入方式&#xff0c;分别是: setter注入 简单类型引用类型 构造器注入 简单类型引用类型 setter注入 在bean中定义引用类型属性&#xff0c;并提供可访问的set方法配置中使用property标签ref属性注入引用类型对象 (1)项目中添加BookDao、BookDaoIm…

逆向攻防世界CTF系列37-crackme

逆向攻防世界CTF系列37-crackme 参考https://blog.csdn.net/xiao__1bai/article/details/120230397 nspack的壳&#xff0c;查了一下好像是北斗的一个壳 没找到什么脱壳软件&#xff0c;只能手动脱壳了 手动脱壳的最终要的是ESP定律 ESP定律的原理就是“堆栈平衡”原理 涉及…

按钮权限的操作方法

首先先在你的本地储存里边&#xff0c;加入一些你指定的字段 然后创建一个文件夹&#xff0c;在此文件夹下创建一个js文件&#xff0c;文件内容如下 在你所需要隐藏按钮的页面引入此js文件&#xff0c;并且通过 directives自定义指令绑定你的每一个按钮。在js文件中通过三个常量…

vscode 关闭绑定元素 隐式具有“any”类型这类错误

在vue的项目里面&#xff0c;经常看到any类型的报错&#xff0c;真的很烦的 在tsconfig.json中配置以下参数 “noImplicitAny”: false 就可以了 出现类型“never”上不存在属性“userName”。ts-plugin(2339) 配置该参数 modeuleResolution : node "compilerOptions&qu…

springboot 的 Profile

什么是 Profile &#xff1f; 应用所在的运行环境发生切换时&#xff0c;配置文件常常就需要随之修改。 Profile&#xff1a;——就是一组配置文件及组件的集合。 可以整个应用在不同的profile之间切换&#xff08;设置活动profile&#xff09;&#xff0c;整个应用都将使用该…

onvif协议相关:4.1.6 Digest方式云台控制启动

背景 关于onvif的其实很早之前我已经在专栏中写了不少了, 使用onvif协议操作设备 但最近有陆陆续续的粉丝问我, 希望我在写一些关于 onvif的设备自动发现、预置位跳转、云台操作的博客。 满足粉丝的需求,安排。 今天我们来实现 设备云台的控制(启动) 实现 1.在ONVIF Devi…

【JAVA毕业设计】基于Vue和SpringBoot的农机电招平台

本文项目编号 T 615 &#xff0c;文末自助获取源码 \color{red}{T615&#xff0c;文末自助获取源码} T615&#xff0c;文末自助获取源码 随着农机电招行业的不断发展&#xff0c;农机电招在现实生活中的使用和普及&#xff0c;农机电招行业成为近年内出现的一个新行业&#x…

基于Jmeter的分布式压测环境搭建及简单压测实践

写在前面 平时在使用Jmeter做压力测试的过程中&#xff0c;由于单机的并发能力有限&#xff0c;所以常常无法满足压力测试的需求。因此&#xff0c;Jmeter还提供了分布式的解决方案。本文是一次利用Jmeter分布式对业务系统登录接口做的压力测试的实践记录。按照惯例&#xff0…

代码随想录算法训练营day41|动态规划04

最后一块石头的重量|| 返回剩余最后一块石头石头最小的可能重量&#xff0c;那么就应该最后剩余的两块石头尽量都等于或接近总重量的一半&#xff0c;这样剩下的就是一半的质量 目标和 给定一个非负整数数组&#xff0c;a1, a2, …, an, 和一个目标数&#xff0c;S。现在你有…

Python+Flask实现随机选谷票游戏

西方曾进行一项著名的投资随机性实验&#xff0c;对比基金经理与猴子在选股上的表现。 实验方法&#xff1a;主持人提供一系列股票&#xff0c;基金经理依靠其专业知识&#xff08;如财务报表、行业趋势、产品市场及公司文化与管理层分析等&#xff09;进行筛选&#xff1b;而…