C语言详解判断相同树案例分析

目录
  • 一、题目描述
  • 二、解题思路

题目难度：简单

一、题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

LeetCode链接：相同的树

二、解题思路

核心思路：

先比较两颗二叉树的根节点

  • 如果「都为空」，则返回 true，说明两树相同。
  • 如果「一个为空一个不为空」，说明这两颗树不相同，则返回 false。
  • 如果「都不为空，但节点值不相同」，说明这两颗树不相同，则返回 false。
  • 经过 1 和 2 和 3 的判断，说明根节点「都不为空，但节点值相同」，则当前节点相同。我们继续递归遍历，比较它的左子树和右子树的根节点。

递归过程演示：

依次比较两颗二叉树中「当前树(1、2、3、4、5、6)的根节点」是否相等，这样每个节点都被比较了一次。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    // 1. 先比较两颗树的根节点
    // 都为空，返回true，说明满足相同的树的条件
    if(p == NULL && q == NULL)
    {
        return true;
    }
    // 一个为空一个不为空，返回false
    if(p == NULL || q == NULL)
    {
        return false;
    }
    // 都不为空，但节点值不相等，返回false
    if(p->val != q->val)
    {
        return false;
    }
    // 2. 经过前面的if的判断，既然运行到这里了，说明当前节点相等
    // 则继续比较左子树和右子树的根节点
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

时间复杂度：假设两棵树都有 n 个节点，最多比较 n 次，所以为 O ( N ) O(N) O(N)

空间复杂度：往下递归会开辟栈帧空间，函数返回时会还给操作系统，所以「空间复杂度」和「递归的最大深度」有关，最坏情况下，「递归的最大深度」就是有 n 的节点二叉树的最大深度，所以为 O ( N ) O(N) O(N)

  • 最大深度： 此树为单边树，则深度为 n，最多向下创建 n 个栈帧，因为栈帧会边用边销毁
  • 最小深度： 此树为完全二叉树/满二叉树，则深度为 log2(N+1)

到此这篇关于C语言详解判断相同树案例分析的文章就介绍到这了,更多相关C语言判断相同树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(100.判断相同树)

    [LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

  • C语言详解判断相同树案例分析

    C语言详解判断相同树案例分析

    目录 一.题目描述 二.解题思路 题目难度:简单 一.题目描述 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同. 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的. LeetCode链接:相同的树 二.解题思路 核心思路: 先比较两颗二叉树的根节点 如果「都为空」,则返回 true,说明两树相同. 如果「一个为空一个不为空」,说明这两颗树不相同,则返回 false. 如果「都不为空,但节点值不相同」,说明这两颗树不相同,则返回 false. 经过 1 和

  • C语言详解如何应用模拟字符串和内存函数

    C语言详解如何应用模拟字符串和内存函数

    目录 1.strlen 求字符串长度 使用案例: 1.计数法 2.不创建临时变量计数器-递归 3.指针-指针的方式 2.长度不受限制的字符串函数 1.strcpy 使用案例: 模拟实现: 2.strcat 使用案例: 模拟实现: 3.strcmp-比较字符串首字母的大小 使用案例: 模拟实现: 3.长度受限制的字符串函数  1.strncpy 使用案例: 2.strncat  使用案例: 3.strncmp 使用案例: 4.strstr-找子串  使用案例: 模拟实现: 5.strtok 用法:

  • C语言详解如何实现堆及堆的结构与接口

    C语言详解如何实现堆及堆的结构与接口

    目录 一.堆的结构及实现(重要) 1.1 二叉树的顺序结构 1.2 堆的概念及结构 1.3 堆的实现 1.3.1 堆的向下调整算法 1.3.2 向下调整算法的时间复杂度 1.3.3 堆的创建(向下调整) 1.3.4 堆排序 1.3.5 建堆的时间复杂度 二.堆的相关接口实现(以大堆为例) 2.1 堆的初始化 2.2 堆的销毁 2.3 堆的插入 2.4 堆的删除 2.5 获取堆顶元素 2.6 堆的判空 2.7 找出堆中前k个最大元素 2.8 堆的创建(向上调整) 一.堆的结构及实现(重要) 1.1

  • C语言详解实现链式二叉树的遍历与相关接口

    C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

  • C语言详解数据结构与算法中枚举和模拟及排序

    C语言详解数据结构与算法中枚举和模拟及排序

    目录 枚举 连号区间数 递增三元组 二分 双指针 前缀和 模拟 特别数的和 错误票据 排序 快速排序 归并排序 枚举 连号区间数 来源:第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • C语言详解如何实现带头双向循环链表

    目录 创建链表存储结构 创建结点 链表的初始化 双向链表的打印 双向链表尾插 双向链表尾删 双向链表头插 双向链表头删 双向链表查找 双向链表pos前插入结点 双向链表删除pos位置的结点 双向链表的销毁 顺序表和链表的区别 2022042311415360.{C}{C}png" /> 创建链表存储结构 我们需要创建一个结构体来存储一个链表结点的相关信息. typedef int ListDataType;//将ListDataType先定义为int类型,根据需要可以改为不同的类型 //创

  • C语言详解如何实现顺序栈

    目录 顺序栈的定义 顺序栈的理解 准备工作 具体实现 今天说的是关于数据结构顺序栈的一些基本操作c语言实现. 顺序栈的定义 首先,我们先来简单了解一下顺序栈,前面线性表我们知道,根据顺序存储或者链式存储分为顺序表和单链表,同样的,根据存储方式的不同,我们把栈分为顺序存储的栈称为顺序栈,链式存储的栈称为链栈.我们要讲的就是顺序栈.实际上,有了前面线性表的一些知识后,关于栈的操作我们还是比较容易理解的. 顺序栈的理解 问题来了?我们怎么去定义呢?通常我们可以用一个数组和记录栈顶元素位置的变量组成,栈

  • C语言详解Z字形变换排列的实现

    C语言详解Z字形变换排列的实现

    目录 方法一 方法二 题目链接:Z 字形变换 方法一 ——找规律模拟数组 题目要求构造一个从左到右的Z型矩阵. 通过分析,可以看出这个Z型矩阵的特点 Z型矩阵就是如图中的橙色,绿色这样部分组合在一起的,Z型矩阵就是由一个个这样相同周期组成的. 这里有一种情况需要特殊讨论,当矩阵只有一行时,直接返回原字符. 其余情况均可满足. 其周期的构成满足这样一个规律: 在第一列向下填写矩阵行数r个字符,接着向其右上部分共(r-2)列分别填写一个字符.Z型矩阵的周期t=r+r-2=2*r-2,每个周期会占用矩

  • C语言详解select函数的使用

    C语言详解select函数的使用

    目录 select select API介绍 select 代码 编译运行: select和poll缺点 select select API介绍 主旨思想: 首先要构造一个关于文件描述符的列表,将要监听的文件描述符添加到该列表中. 调用一个系统函数,监听该列表中的文件描述符,直到这些描述符中的一个或者多个进行I/O操作时,该函数才返回. a. 这个函数是阻塞 b. 函数对文件描述符的检测的操作是由内核完成的 在返回时,它会告诉进程有多少(哪些)描述符要进行I/O操作. // sizeof(fd_

  • 详解Java前缀树Trie的原理及代码实现

    目录 Trie的概念 Trie的实现 基本结构 构建Trie 查找字符串 Trie的总结 Trie的概念 Trie(发音类似 “try”)又被称为前缀树.字典树.Trie利用字符串的公共前缀来高效地存储和检索字符串数据集中的关键词,最大限度地减少无谓的字符串比较,其核心思想是用空间换时间. Trie树可被用来实现字符串查询.前缀查询.词频统计.自动拼写.补完检查等等功能. Trie树的三个性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符. 从根节点到某一节点,路径上经过的字符连接起

随机推荐