C语言单值二叉树真题讲解

2024-10-19 13:23:28

一、题目描述

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

二、解题思路

二叉树的递归遍历，一般都会把问题拆分成当前树(根节点) 和子树，然后子树又进行拆分，来解决问题。

核心思路：

1.先判断当前节点是否为空，如果为空，返回 true（空树也满足单值二叉树的条件）

2.判断当前树是不是单值二叉树：

先判断当前节点的左孩子是否为空；
将当前节点的值与左孩子的值进行比较，如果相等，在右孩子不为空的情况下，继续与右孩子的值进行比较；
如果不相等，说明当前树不是单值二叉树，返回 false。

3.继续往下递归遍历，判断当前节点的左右子树是不是单值二叉树。

递归过程演示：

如果 a == b && a == c 为真，说明 1 是单值二叉树。

分而治之，不断迭代，先判断 1 是不是单值二叉树，再判断 2 是不是单值二叉树，最后判断 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. 判断当前节点和其左右孩子是否是单值二叉树
    // 先判断当前节点的左孩子是否为空，并将当前节点的值与左孩子的值进行比较，看是否相等，
    // 如果相等，则继续往下遍历；如果不相等，说明不是单值二叉树，则返回false。
    if(root->left && root->val != root->left->val)
    {
        return false;
    }
    if(root->right && root->val != root->right->val)
    {
        return false;
    }
    // 3. 往下遍历，判断当前节点的左右子树是不是单值二叉树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

代码中有个小思路，我们 if 的条件写的是，如果左孩子不为空，且当前节点的值 != 左孩子的值，则返回 false，那为什么不写成：如果左孩子不为空，且当前节点的值 == 左孩子的值，则怎么怎么样……呢？因为写 ==，不能直接得出一个结果，而写 !=，就能得出结果 flase。

到此这篇关于C语言单值二叉树真题讲解的文章就介绍到这了,更多相关C语言单值二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言数据结构二叉树之堆的实现和堆排序详解

目录一.本章重点二.堆 2.1堆的介绍 2.2堆的接口实现三.堆排序一.本章重点堆的介绍堆的接口实现堆排序二.堆 2.1堆的介绍一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数
C语言数据结构之二叉树详解

目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵
C语言数据结构系列篇二叉树的遍历

目录前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.
C语言二叉树的遍历示例介绍

在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef
C语言超详细总结讲解二叉树的概念与使用

目录 1.二叉树的概念及结构 2.二叉树链式结构的实现 1.二叉树的概念及结构 ①概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成. ②二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点.(度最多为2) 二叉树的子树有左右之分,其子树的次序不能颠倒. ③现实中的二叉树: 当一名普通的人看到这样一颗树,可能会想:好标准的一棵树当一个程序猿看到这样一棵树,可能会想:好像数据结构中的二叉树,并且还是颗满二叉树 ④数据结
C语言深入浅出解析二叉树

目录树概念及结构相关概念树的表示树在实际中的运用(表示文件系统的目录树结构) 二叉树概念及结构概念需要注意的特殊二叉树二叉树的性质二叉树的存储结构顺序存储链式存储总结树概念及结构树是一种非线性的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的注意: 有一个特殊的结点,称为根结点,根节点没有前驱结点除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.
C语言平衡二叉树真题练习

目录一.题目描述二.解题思路自顶向下的递归(暴力解法) 自底向上的递归(最优解法) 题目难度:简单 LeetCode链接:平衡二叉树一.题目描述给定一个二叉树,判断它是否是高度平衡的二叉树. 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 . 二.解题思路一棵二叉树是平衡二叉树,当且仅当其所有子树也都是平衡二叉树,因此我们使用递归的方式依次判断其所有子树是否为平衡二叉树,就知道这棵二叉树是不是平衡二叉树了. 自顶向下的递归(暴力解法)
C语言单值二叉树真题讲解

目录一.题目描述二.解题思路 [OJ - 二叉树]单值二叉树 LeetCode链接:单值二叉树题目难度:简单一.题目描述如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树. 只有给定的树是单值二叉树时,才返回 true:否则返回 false. 二.解题思路二叉树的递归遍历,一般都会把问题拆分成当前树(根节点) 和子树,然后子树又进行拆分,来解决问题. 核心思路: 1.先判断当前节点是否为空,如果为空,返回 true(空树也满足单值二叉树的条件) 2.判断当前树是不是
Java数组与二维数组及替换空格实战真题讲解

目录数组中重复的数字题目描述思路详解代码与结果二维数组中的查找题目描述思路详解代码与结果替换空格题目描述思路详解代码与结果数组中重复的数字题目描述思路详解本题的思路比较简单,首先将这个数组排序,遍历数组,找到当前的和前一个相同的直接输出就好了.没找到输出-1. 注意:这个方法要注意循环的时候下标要从1开始哦,不然会报数组下标异常滴. 代码与结果 import java.util.*; public class Solution { /** * 代码中的类名.方法名
C语言利用面试真题理解指针的使用

目录前言笔试题一笔试题二笔试题三笔试题四笔试题五笔试题六笔试题七笔试题八前言大家好~我又来了,今天给大家带来的是指针的几道笔试题,希望能够加强大家对指针知识的把握,指针就应该这样学! 笔试题一 #include<stdio.h> int main() { int a[5] = { 1 , 2 , 3 , 4 , 5 }; int* ptr = (int*) (&a + 1); printf("%d, %d", *(a + 1), *(ptr -
C语言实例真题讲解数据结构中单向环形链表

目录 1.例题引入 2.何为带环链表 3.题解思路 4.拓展问题目录 1.例题引入链接直达: 环形链表题目: 2.何为带环链表正常的单链表每个节点顺次链接,最后一个节点指向NULL,如下: 而带环链表的最后一个节点不再指向NULL了,指向的是前面任意一个节点,以此形成带环链表,并一直循环下去.如下: 3.题解思路我们可以将上述图画的抽象一点,在没有进入环之前我们用直线表示,进入环之后用圈来表示,以此示意循环.此题需要用到我们之前讲解的求中间节点和求倒数第k个节点的快慢指针的思想.定义两
C语言经典顺序表真题演练讲解

目录 1.移除元素 2.删除有序数组中的重复项 3.合并两个有序数组 1.移除元素链接直达: https://leetcode-cn.com/problems/remove-element/ 题目: 思路: 法一:依次挪动数据进行覆盖从第一个数据开始进行依次遍历,如同示例1,依次遍历数组,找到移除的元素2就把后面的数据往前挪动进行覆盖,如图所示: 此法有个缺陷,题目中明确指出使用空间复杂度O(1)的方法解决此问题,而此法的空间复杂度刚好为O(1),可以解决,不过考虑周全些,时间复杂度在情况最
Go语言切片常考的面试真题解析

目录前言 01. 数组和切片有什么区别? 02. 拷贝大切片一定比拷贝小切片代价大吗? 03. 切片的深浅拷贝 04. 零切片.空切片.nil切片是什么 05. 切片的扩容策略 07. 参数传递切片和切片指针有什么区别? 08. range遍历切片有什么要注意的? 总结前言哈喽,大家好,我是asong.最近没事在看八股文,总结了几道常考的切片八股文,以问答的方式总结出来,希望对正在面试的你们有用- 本文题目不全,关于切片的面试真题还有哪些?欢迎评论区补充- 01. 数组和切片有什么区别?
C语言修炼之路函数篇真题训练下

本文的Gitee地址:文章源代码第壹题 :字符串逆序(递归实现) 方法一,非递归实现 main主体部分数组名是首元素的地址首元素是char类型,对应的传参元素过去就是 char* 类型采用两个指针不断移动,然后交换两个位置的元素来实现逆序方法贰,递归实现大致思路代码实现 (推荐自己手动模拟一下) void reverse_string(char* str) { int len = strlen(str); char tmp = str[0]; str[0] = str[le
C语言修炼之路函数篇真题训练上

本文对应文章 : C语言修炼之路一朝函数思习得模块思维世间生上篇 C语言修炼之路一朝函数思习得模块思维世间生下篇第壹题 A选项 C语言的函数每次只能返回一个元素,上面代码中的 return a,b 只能执行逗号表达式的最后一个语句,即返回20 B选项 C选项 D选项全局变量在整个程序的任意地方都可以使用第贰题 C选项函数不可嵌套定义,但可以嵌套调用 -- “上一篇文章中提及过” 第叁题 A选项可以 return void 不返回任何参数 B选项正确 C选项可以使用全局变量
C语言实题讲解快速掌握单链表下

目录 1.移除链表元素 2.反转链表 3.链表的中间节点 4.链表中倒数第k个节点 5.合并两个有序链表 6.链表分割 1.移除链表元素链接直达: 移除链表元素题目: 思路: 此题要综合考虑多种情况,常规情况就如同示例1,有多个节点,并且val不连续,但是非常规呢?当val连续呢?当头部就是val呢?所以要分类讨论常规情况: 需要定义两个指针prev和cur,cur指向第一个数据,prev指向cur的前一个.依次遍历cur指向的数据是否为val,若是,则把prev的下一个节点指向cur的下

C语言单值二叉树真题讲解

目录

一、题目描述

二、解题思路

相关推荐

随机推荐