【LeetCode】链式二叉树OJ题---C语言版

链式二叉树OJ题

  • 一、单值二叉树
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 二、二叉树最大深度
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 三、检查两颗树是否相同
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 四、二叉树的前序遍历
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 五、翻转二叉树
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 六、另一颗树的子树
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：
  • 七、二叉树的构建及遍历
    • （1）题目描述：
    • （2）思路表述：
    • （3）代码实现：

一、单值二叉树

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

  1. 如果传回来是空节点，那么就返回真。
  2. 如果传过来只有一个节点，那么我们也返回真
  3. 首先我们应该先判断不相等的，因为相等的他肯定要递归嘛（最值得注意的是，你得先判断这个左/右子树，它存在不存在！只有左/右子树存在了，才能判断左/右子树中的值跟它的根节点是否相等。如果左子树不存在，我们都不需要判断它！如果左子树不存在，我们就直接访问空了，这样会报错的。）
  4. 如果以上的三种情况都不符合的话，我们就继续递归往下走。

（3）代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) 
{
    //1.如果传回来是空节点，那么就返回真。
   if(root==NULL)
   {
       return true;
   }
   //2.如果传过来只有一个节点，那么我们也返回真
   if(root->left==NULL&&root->right==NULL)
   {
       return true;
   }
   //3.首先我们应该先判断不相等的，因为相等的他肯定要递归嘛
   //最值得注意的是，你得先判断这个左/右子树，它存在不存在！只有左/右子树存在了，才能判断左/右子树中的值跟它的根节点是否相等。如果左子树不存在，我们都不需要判断它！如果左子树不存在，我们就直接访问空了，这样会报错的。
   if(root->left&&root->left->val!=root->val)
   {
       return false;
   }
   else if(root->right&&root->right->val!=root->val)
   {
       return false;
   }

    //4.如果以上的三种情况都不符合的话，我们就继续递归往下走。
   return isUnivalTree(root->left)&&isUnivalTree(root->right);

}

二、二叉树最大深度

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

从根开始分别遍历左子树和右子树，取最大的就是整个树的最大深度

递归展开图理解：
在这里插入图片描述

（3）代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int maxDepth(struct TreeNode* root) 
{
    if(root==NULL)
    {
        return 0;
    }

    return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}

三、检查两颗树是否相同

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

1.如果两个二叉树都为空，则两个二叉树相同。
2.如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

3.如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

（3）代码实现：

/**
 * 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)//if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))
    {
        return false;
    }
    //两个都不为空
    //1.先判断不相等
    if(p->val!=q->val)
    {
        return false;
    }
    //2.如果相等
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);

}

四、二叉树的前序遍历

（1）题目描述：

点击链接

在这里插入图片描述

（2）思路表述：

  1. 创建一个刚好满足所有储存树的结点的数组空间大小
  2. 以前序的方式把树中的结点依次放入数组中

（3）代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}


void Prevorder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    arr[(*i)++]=root->val;
    Prevorder(root->left,arr,i);
    Prevorder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //1.创建一个刚好满足所有储存树的结点的数组空间大小
    int n=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*n);

    int i=0;

    //2.以前序的方式把树中的结点依次放入数组中
    Prevorder(root,arr,&i);

    *returnSize=n;
    return arr;
}

五、翻转二叉树

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

  1. 我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转
  2. 一直遍历到树的的叶子节点
  3. 如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

不理解的时候：就画递归展开图就行！

（3）代码实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 //不理解的时候：就画递归展开图就行！
struct TreeNode* invertTree(struct TreeNode* root) 
{
    if(root==NULL)
    {
        return NULL;
    }
    //我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转
    struct TreeNode* left=invertTree(root->left);//一直遍历到树的的叶子节点
    struct TreeNode* right=invertTree(root->right);

    root->left=right;
    root->right=left;


//如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

    return root;
   
}

六、另一颗树的子树

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

  1. 如果root为NULL，我们就返回空：NULL

  2. 首先我们先判断刚开始的root和subroot的根相不相等？如果相等，然后再判断是否是相同的树

  3. 如果刚开始root->val!=subroot->val，不要着急!继续遍历root的左，右子树

（3）代码实现：

/**
 * 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)//if((p==NULL&&q!=NULL)||(p!=NULL&&q==NULL))
    {
        return false;
    }
    //两个都不为空
    //1.先判断不相等
    if(p->val!=q->val)
    {
        return false;
    }
    //2.如果相等
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);

}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL)
    {
        return false;
    }

    //2.首先我们先判断刚开始的root和subroot的根相不相等？如果相等，然后再判断是否是相同的树
    if(root->val==subRoot->val)
    {
        if(isSameTree(root,subRoot))
        {
            return true;
        }

        //return isSameTree(root,subRoot);不能这样写，因为如果这样写的话,可能root的下面可能有子树和传过来的subroot是相同的树，
        //但是你没有判断，直接return返回了，这样就有所欠缺!

        
    }
    //3.如果刚开始root->val!=subroot->val，不要着急!继续遍历root的左，右子树
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

}

七、二叉树的构建及遍历

（1）题目描述：

点击链接
在这里插入图片描述

（2）思路表述：

  1. 读入字符串
  2. 创建二叉树
  3. 中序打印二叉树

（3）代码实现：

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

//MakeTree函数的意义在于将数组中的数据，以前序的方式创建一棵树
TreeNode* MakeTree(char* arr,int* n)
{
    if((arr[*n]=='#')||(arr[*n]=='\0'))
    {
        return NULL;
    }
    //我要将数组中的数据放入树中的前提：是我要先创造一个树。
    TreeNode* newtree=(TreeNode*)malloc(sizeof(TreeNode));
    newtree->val=arr[(*n)++];

    //newtree->left=MakeTree(arr,(*n)++);
    newtree->left=MakeTree(arr,n);
    (*n)++;
    newtree->right=MakeTree(arr,n);

    return newtree;
}

void InOrder(TreeNode* tree)
{
    if(tree==NULL)

    {
        return ;
    }
    InOrder(tree->left);
    printf("%c ",tree->val);
    InOrder(tree->right);
}

int main() {
    //int n = 0;
    //TreeSize(n);
    //int* arr = (int*)malloc(sizeof(int) * n);
    //scanf("%s", arr);
    char arr[101];
    scanf("%s",arr);
    int n=0;
    //创建一个n,作为一个我创建树的时候的一个标记指针，如果遇到空或者结尾的时候会返回
    TreeNode* tree=MakeTree(arr,&n);

    InOrder(tree);
    return 0;
}

好了，今天的分享就到这里了
如果对你有帮助，记得点赞👍+关注哦！
我的主页还有其他文章，欢迎学习指点。关注我，让我们一起学习，一起成长吧！
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

java学习part26线程安全

java学习part26线程安全

136-多线程-同步代码块解决两种线程创建方式的线程安全问题_哔哩哔哩_bilibili 1.安全问题 关键在于某些数据操作 2.解决 2.1同步代码块 相当于给数据操作加了互斥锁 2.1.1在实现runnable接口的方式下 锁对象要求必须是唯一的&#xff0c;因为可以看成是谁占了这个对象&…
阅读更多...
SpringBoot 是如何启动一个内置的Tomcat

SpringBoot 是如何启动一个内置的Tomcat

为什么说Spring Boot框架内置Tomcat 容器，Spring Boot框架又是怎么样去启动Tomcat的？我简单总结下学习过程。 一：简单了解SpringBoot的启动类 我们都知道Spring Boot框架的启动类上是需要使用 @SpringBootApplication 注解标注的， @SpringBootApplication 是一个复合注解…
阅读更多...
Jupyter Markdown 插入图片

Jupyter Markdown 插入图片

首先截图 注意 这一步是关键的&#xff01;&#xff01; 它需要使用电脑自带的截图&#xff0c;用qq啊vx啊美图秀秀那些都不行哦。 截图之后复制&#xff1a; 然后快捷键粘贴到jupyter里面&#xff0c;它会生成一段代码&#xff08;没有代码就是说截图形式不对&#xff09;&a…
阅读更多...
深入计算机系统看性能优化

深入计算机系统看性能优化

一&#xff0e;引言 “性能优化”&#xff0c;从计算机诞生之初就一直伴随着计算机技术的发展&#xff0c;直到现在。将来也必定不会消失。这是因为每个人都会追求性价比&#xff0c;花最少的钱&#xff0c;办最多的事。生活中也一样&#xff0c;就比如说泡茶&#xff0c;但凡…
阅读更多...
2023年12月03日新闻简报（国内国际）

2023年12月03日新闻简报（国内国际）

新闻简报 每天三分钟&#xff0c;朝闻天下事。今天是&#xff1a;2023年12月03日&#xff0c;星期日&#xff0c;农历十月廿一&#xff0c;祝工作愉快&#xff0c;身体健康&#xff0c;生活喜乐&#xff1a; &#x1f449;&#x1f449;国内新闻 1、1日凌晨&#xff0c;四川…
阅读更多...
docker-速通

docker-速通

1.命令-镜像操作 docker pull nginx #下载最新版 docker pull nginx:1.20.1 #下载指定版本 镜像名:版本名&#xff08;标签&#xff09; docker images #查看所有镜像 # 如果只写镜像名实际就是redis redis:latest 记住这个不是命令 docker rmi 镜像名:版本号/镜像id…
阅读更多...
Pandas教程06：DataFrame.merge数据的合并处理

Pandas教程06：DataFrame.merge数据的合并处理

DataFrame.merge() 是 pandas 库中用于合并两个DataFrame数据的方法。该方法主要用于根据一个或多个键&#xff08;键可以是列名或索引&#xff09;将两个 DataFrame 连接在一起&#xff0c;这个过程类似于 SQL 中的 JOIN 操作。 #我的Python教程 #微信公众号&#xff1a;wdPy…
阅读更多...
【PTA-C语言】实验四-循环结构II

【PTA-C语言】实验四-循环结构II

如果代码存在问题&#xff0c;麻烦大家指正 ~ ~有帮助麻烦点个赞 ~ ~ 实验四-循环结构II 7-1 跟奥巴马一起画方块&#xff08;分数 15&#xff09;7-2 打印九九口诀表&#xff08;分数 10&#xff09;7-3 求符合给定条件的整数集&#xff08;分数 15&#xff09;7-4 求特殊方程…
阅读更多...
网络虚拟化场景下网络包的发送过程

网络虚拟化场景下网络包的发送过程

网络虚拟化有和存储虚拟化类似的地方&#xff0c;例如&#xff0c;它们都是基于 virtio 的&#xff0c;因而在看网络虚拟化的过程中&#xff0c;会看到和存储虚拟化很像的数据结构和原理。但是&#xff0c;网络虚拟化也有自己的特殊性。例如&#xff0c;存储虚拟化是将宿主机上…
阅读更多...
爬虫学习-基础（HTTP原理）

爬虫学习-基础（HTTP原理）

目录 一、URL和URI 二、HTTP和HTTPS &#xff08;1&#xff09;HTTP &#xff08;2&#xff09;HTTPS &#xff08;3&#xff09;HTTP与HTTPS区别 &#xff08;4&#xff09;HTTPS对HTTP的改进&#xff1a;双问的身份认证 三、TCP协议 &#xff08;1&#xff09;TCP三次握手…
阅读更多...
2000-2021年上市公司过度负债数据

2000-2021年上市公司过度负债数据

2000-2021年上市公司过度负债数据 1、时间&#xff1a;2000-2021年 2、指标&#xff1a; 证券代码、证券简称、会计期间、上市日期、行业代码、行业名称、是否剔除ST或*ST股、是否剔除当年新上市、已经退市或被暂停退市的公司、产权性质、盈利能力、杠杆率行业中位数、成长性…
阅读更多...
ELK高级搜索，深度详解ElasticStack技术栈-下篇

ELK高级搜索，深度详解ElasticStack技术栈-下篇

前言&#xff1a;ELK高级搜索&#xff0c;深度详解ElasticStack技术栈-上篇 14. search搜索入门 14.1. 搜索语法入门 14.1.1 query string search 无条件搜索所有 GET /book/_search结果&#xff1a; {"took" : 969,"timed_out" : false,"_shar…
阅读更多...
架构图是什么，怎么做？

架构图是什么，怎么做？

架构图是一种用来描述系统或软件的结构和组成的图形表示。它展示了系统中各个组件之间的关系、交互和功能。通过绘制架构图&#xff0c;可以更好地理解和沟通系统的设计和实现。 绘制架构图的软件 目前市场上有许多用于绘制架构图的软件工具&#xff0c;下面简单…
阅读更多...
Conmi的正确答案——“xxx.sh: 行 2: $‘\r‘: 未找到命令”

Conmi的正确答案——“xxx.sh: 行 2: $‘\r‘: 未找到命令”

Ubuntu版本&#xff1a;23.10&#xff08;桌面版&#xff09; 问题原因&#xff1a; 这个sh文件被window编辑后会以DOS格式保存&#xff0c;但linux格式中回车只认“\n”&#xff0c;而DOS格式的回车则是“\r\n”。 解决方案&#xff1a; 使用nano打开一次文件&#xff0c;并且…
阅读更多...
有两个篮子，分别为A 和 B，篮子A里装有鸡蛋，篮子B里装有苹 果，请用面向对象的思想实现两个篮子里的物品交换

有两个篮子，分别为A 和 B，篮子A里装有鸡蛋，篮子B里装有苹 果，请用面向对象的思想实现两个篮子里的物品交换

问题&#xff1a; 有两个篮子&#xff0c;分别为A 和 B&#xff0c;篮子A里装有鸡蛋&#xff0c;篮子B里装有苹 果&#xff0c;请用面向对象的思想实现两个篮子里的物品交换 代码 package cn.ljh.algorithmic;/*** author JH*/ public class Demo07 {public static void main…
阅读更多...
git rebase冲突说明（base\remote\local概念说明）

git rebase冲突说明（base\remote\local概念说明）

主线日志及修改 $ git log master -p commit 31213fad6150b9899c7e6b27b245aaa69d2fdcff (master) Author: Date: Tue Nov 28 10:19:53 2023 08004diff --git a/123.txt b/123.txt index 294d779..a712711 100644 --- a/123.txtb/123.txt-1,3 1,4 123 4^Mcommit a77b518156…
阅读更多...
使用SpringBoot和ZXing实现二维码生成与解析

使用SpringBoot和ZXing实现二维码生成与解析

一、ZXing简介 ZXing是一个开源的&#xff0c;用Java实现的多种格式的1D/2D条码图像处理库。它包含了用于解析多种格式的1D/2D条形码的工具类&#xff0c;目标是能够对QR编码&#xff0c;Data Matrix, UPC的1D条形码进行解码。在二维码编制上&#xff0c;ZXing巧妙地利用构成计…
阅读更多...
【Linux】命令行参数

【Linux】命令行参数

文章目录 前言一、C语言main函数的参数二、环境变量总结 前言 我们在Linux命令行输入命令的时候&#xff0c;一般都会跟上一些参数选项&#xff0c;比如l命令&#xff0c;ls -a -l。以前我总是觉得这是理所当然的&#xff0c;没深究其本质究竟是什么&#xff0c;今天才终于知道…
阅读更多...
180天Java从小白到就业-Day03-03Java位运算符、赋值运算符、数据交换的三种方式

180天Java从小白到就业-Day03-03Java位运算符、赋值运算符、数据交换的三种方式

1. 位运算符 Q&#xff1a;为什么要学习位运算 A&#xff1a;由于其运算效率更高&#xff0c;在JDK源码&#xff08;例如ArrayList、HashMap&#xff09;中大量使用位运算&#xff0c;想要看懂JDK源码必须懂位预算&#xff0c;但是在公司开发业务系统时位运算使用并不多。 Q…
阅读更多...
N-135基于springboot,vue高校图书馆管理系统

N-135基于springboot,vue高校图书馆管理系统

开发工具&#xff1a;IDEA 服务器&#xff1a;Tomcat9.0&#xff0c; jdk1.8 项目构建&#xff1a;maven 数据库&#xff1a;mysql5.7 系统分前后台&#xff0c;项目采用前后端分离 前端技术&#xff1a;vueelementUI 服务端技术&#xff1a;springbootmybatisredis 本项…
阅读更多...
最新文章

Copyright @ 2022~2023