相同的树 单值二叉树 二叉树的最大深度

简介: 相同的树 单值二叉树 二叉树的最大深度

相同的树


力扣:100相同的树

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

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

示例 1:

输入:p = [1,2,3], q = [1,2,3]

输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]

输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]

输出:false


提示:


两棵树上的节点数目都在范围 [0, 100] 内

-104 <= Node.val <= 104


分析:


如果两个二叉树都为空,那么这两个二叉树必定相同


如果这两个二叉树一个为空,另一个不为空,那么两个二叉树必定不相等


如果两个二叉树都不为空,那么就判断根节点是否相同:如果不相同,那么两个二叉树必定不相同;如果相同,再去遍历两个二叉树的左子树和右子树。


这是一个递归的过程,也是分治思想,都是去判断两个二叉树自己(根节点)的值是否相同,然后再去遍历左右子树,不是左右孩子。


代码:

/**
 * 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);
}


单值二叉树


单值二叉树

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

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

示例 1:

输入:[1,1,1,1,1,null,1]

输出:true

示例 2:

输入:[2,2,2,5,2]

输出:false

提示:

给定树的节点数范围是 [1, 100]。

每个节点的值都是整数,范围为 [0, 99] 。

分析:

单值二叉树,即树上的每个节点的值都是同一个数

检查自己和他的孩子是否相等,如果不相等则返回false;如果相等,则继续遍历左右子树,依然是一个递归过程


代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
        return true;
    if(root->left&&root->left->val!=root->val)
        return false;
    if(root->right&&root->right->val!=root->val)
        return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}


二叉树的最大深度


二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

输入:root = [3,9,20,null,null,15,7]

输出:3

示例 2:


输入:root = [1,null,2]

输出:2


提示:


树中节点的数量在 [0, 104] 区间内。

-100 <= Node.val <= 100


分析:


递归计算出左右子树的最大深度,然后即可算出最大深度


代码:

/**
 * 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;
}
目录
相关文章
【每日一题Day282】LC2681英雄力量 | 排序+数学
【每日一题Day282】LC2681英雄力量 | 排序+数学
74 0
|
编解码 算法 计算机视觉
HSV
HSV
530 4
|
搜索推荐 API 语音技术
FunClip的基础功能问题之使用FunClip进行智能剪辑的问题如何解决
FunClip的基础功能问题之使用FunClip进行智能剪辑的问题如何解决
1099 0
|
12月前
|
存储 Java Android开发
深入理解移动应用开发:从基础到高级
【10月更文挑战第6天】在这篇文章中,我们将深入探讨移动应用开发的世界。我们将从基础开始,包括移动操作系统的基本知识,然后逐步深入到更复杂的主题,如移动应用的开发和优化。我们将通过代码示例来展示这些概念,使读者能够更好地理解和应用这些知识。无论你是初学者还是有经验的开发者,这篇文章都将为你提供有价值的信息和见解。
|
存储 弹性计算 Linux
Linux:进程调度
Linux:进程调度
128 7
R语言分位数回归、GAM样条曲线、指数平滑和SARIMA对电力负荷时间序列预测
R语言分位数回归、GAM样条曲线、指数平滑和SARIMA对电力负荷时间序列预测
|
容器 Kubernetes Perl
从零开始入门 K8s| 阿里技术专家详解 K8s 核心概念
作者| 阿里巴巴资深技术专家、CNCF 9个 TCO 之一 李响 一、什么是 Kubernetes Kubernetes,从官方网站上可以看到,它是一个工业级的容器编排平台。Kubernetes 这个单词是希腊语,它的中文翻译是“舵手”或者“飞行员”。
18924 1
|
Java Maven
Maven变量定义
Maven变量定义
|
监控 前端开发 搜索推荐
智能呼叫系统关键技术
一、呼叫系统关键技术   一个完整的呼叫系统,一般由PBX(程控交换机)、ACD(自动呼叫分配)交换机、IVR(交互式语音应答)系统、CTI(计算机电话呼叫系统集成)系统、数据库系统、呼叫管理系统、业务处理系统以及座席(业务代表)等组成。用户的呼叫在ACD交换机排队之后,引导到不同的人工受理席,然后以语音或传真等不同方式给予用户相关的业务答复。系统大致可以分为前端和后端两大部分。在系统前   端,CTI是其核心,在计算机与电话呼叫系统集成的基础之上对客户的呼叫进行应答、识别、接续、转移等受理活动;系统后端主要由各种数据库系统如账务系统、业务管理系统以及网络软硬件提供业务支持,保障数据的正确性和
求Fibonacci数列前20项:利用数组
求Fibonacci数列前20项:利用数组
341 0