二叉树的OJ练习(一)

简介: 二叉树的OJ练习(一)


<你想看的我这里都有😎 >

单值二叉树

965. 单值二叉树 - 力扣(LeetCode)

题目:如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回 true;否则返回 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->val!=root->left->val)
        return false;
    if(root->right&&root->val!=root->right->val)
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

解释:

1、首先当树为空树时,并不违反规定,可以直接返回true

2、当不为空树时,先判断其左右子树是否存在,如果左子树不存在,则继续判断右子树是否存在,若两者都不存在则进行下一次的递归判断

3、当左子树存在时,用当前结点的值与其左子树的根结点的值作比较,如果不相等就返回false

4、当右子树存在时,用当前结点的值与其右子树的根结点的值作比较,如果不相等就返回false

相同的树

100. 相同的树 - 力扣(LeetCode)

题目:给你两棵二叉树的根节点 pq ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

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

解释:

1、先比较两个树的根节点,如果均为空,则两树虽为空树,但仍相等,返回true

2、若两个树中的根节点有一个为空,那么两个树一定不相等,返回flase

3、如果两个树的根节点均不为空,比较它们的值,如果不相等返回flase

4、比较完两棵树的根节点后,再比较两颗树的左子树和右子树,即isSameTree(p->left,q->left)与

isSameTree(p->right,q->right)

对称二叉树

101. 对称二叉树 - 力扣(LeetCode)

题目:给你一个二叉树的根节点 root , 检查它是否轴对称

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool judge(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 judge(p->left,q->right) && judge(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    //如果为空树,那么该树就对称
    if(root == NULL)
        return true;
    return judge(root->left,root->right);
}

解释:

1、当一棵树为空树时,该树对称,返回true

2、判断根节点的左右子树的根节点,如果两个结点均为空,则树只有一个根节点,该树对称,然会true

3、如果两个结点只有一个为空,则树不对称,返回false

4、如果两个结点均不为空,且两个结点的值均不相同,树不对称,返回false

5、递归左子树的左子树与右子树的右子树,如果均相同则返回true(重要)

6、递归左子树的右子树与右子树的左子树,如果均相同则返回true(重要)

7、如果两次递归均返回true,则judge函数返回true

总结:对于C语言而言采用这种解法完成本题必须使用两个函数,因为这里的判断二叉树是否对称,不仅仅是要整体上对称,而且值也要对称,如果只能传递一个参数那么就只能先比较完一个完整的左子树然后再去比较另一个完整的右子树,很明显这样无法完成我们的目标的,所以我们要引入一个新的judge函数来获取树的根节点的左右子树的根节点,然后经过一系列基本的判断后,进行那两步十分重要的递归:

二叉树的前序遍历

144. 二叉树的前序遍历 - 力扣(LeetCode)

题目:给你二叉树的根节点 root ,返回它节点值的 前序 遍历

/**
 * 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* a,int* pi)
{
    if(root == NULL)
        return;
    a[(*pi)++] = root->val;
    PrevOrder(root->left,a,pi);
    PrevOrder(root->right,a,pi);
}
//输出型参数returnSize
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int) * n);
    *returnSize = n;
    int i = 0;
    PrevOrder(root,a,&i);
    return a;
}

解释:

1、leetcode题目中常常会出现returnSize,我们叫它输出型参数,在这里它表示要返回二叉树结点的个数,所以我们还需要利用之前学过的TreeSize函数额外的计算二叉树结点的个数,最后将计算的返回值n赋值给*returnSize(returnSize是指针,用*以修改它的值)

2、除了returnSize外,题目要求我们以数组的形式返回二叉树前序遍历的结点,所以我们还要开辟一个数组a,为了确保代码不是硬代码,所以我们使用malloc来开辟数组的空间,开辟的空间大小由我们计算的二叉树结点的个数n决定

3、进行前序遍历时,我们要传入的参数除了二叉树的根节点以外,还需要传入数组a的指针,以及用于表示数组下标的i的地址(i初始化值为0,如果传入的不是地址,当左子树遍历完后开始遍历右子树时,i的值也会回到原来的值而不是递增下去,因为每一次的递归开辟帧栈的过程中,i因为不是全局变量所以每一块的帧栈中都会有一个i,下图中结点1开始递归左右子树时,左子树走到底时i=2,但是右子树中的i存放的依然是刚开始递归时i的值,所以如果开始递归右子树那么3会将原来的2代替,存放二叉树前序遍历结果的数组也就由原来预期的1243变为了134)

4、PrevOrder函数前序遍历时,要注意使用a[(*pi)++] = root->val向数组中存值时,一定要使用(*pi)而非pi(原因就是3中提到的)

~over~

相关文章
|
Oracle Java 关系型数据库
程序员做开发工作必须要考证么?
众所周知,随着信息技术的迅速发展,程序员已经成为现代社会中不可或缺的一部分。与此同时,关于程序员需要考证的话题也越来越受到关注,以及现在互联网行业内卷严重,催生了程序员继续学习的渠道。随着行业寒冬的影响,互联网行业的程序员竞争越来越激烈,也让程序员再次审视了考证提高自身竞争力的设想。那么本文就来简单探讨一下程序员是否需要考证,以及衡量程序员能力的方式是什么?
320 2
程序员做开发工作必须要考证么?
|
机器学习/深度学习 人工智能 分布式计算
跨越时代的数据力量:大规模数据处理的技术突破
在信息爆炸的时代,大规模数据处理成为了推动科技进步的重要驱动力。本文将探讨大规模数据处理所涉及的技术突破,包括分布式计算、机器学习和人工智能等,以及其在各个领域的应用,展现数据的无限潜力。
|
Cloud Native
云原生部署问题之什么是结构体,并给出一个结构体的定义和初始化示例
云原生部署问题之什么是结构体,并给出一个结构体的定义和初始化示例
109 10
|
测试技术
#### [623. 在二叉树中增加一行](https://leetcode.cn/problems/add-one-row-to-tree/)
#### [623. 在二叉树中增加一行](https://leetcode.cn/problems/add-one-row-to-tree/)
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
403 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
存储 安全 前端开发
如何将加密和解密函数应用到实际项目中?
如何将加密和解密函数应用到实际项目中?
197 138
|
9天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
377 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)