当前位置： 首页 > news >正文

二叉树相关的算法题

news 2025/8/10 14:06:14

二叉树相关的算法题

单值二叉树

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

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

示例 1：

在这里插入图片描述

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

在这里插入图片描述

输入：[2,2,2,5,2]
输出：false

提示：

  1. 给定树的节点数范围是 [1, 100]。
  2. 每个节点的值都是整数，范围为 [0, 99] 。

思路如下：

在这里插入图片描述

代码如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
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);
}

相同的树

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

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

示例 1：

在这里插入图片描述

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
在这里插入图片描述

输入：p = [1,2], q = [1,null,2]
输出：false

示例 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){return false;}//值不同if(p->val!=q->val){return false;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
在这里插入图片描述

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

在这里插入图片描述

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

这道题是基于上一题相同的树来完成的。

代码如下：

/*** 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->right)&&isSameTree(p->right,q->left);//不同点在于这里两个树的结构进行比较，不是说树的内部进行比较}
bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left,root->right);
}

另一个树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

在这里插入图片描述

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：
在这里插入图片描述

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -104 <= root.val <= 104
  • -104 <= subRoot.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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL){return false;}if(isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

这几道题我们可以发现重要的规律，都要用到相同的二叉树里面的代码，这里有所不同的地方在于让根节点的左右子树分别和subRoot进行比较。

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

在这里插入图片描述

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

在这里插入图片描述

输入：root = [1,2]
输出：[1,2]

示例 5：
在这里插入图片描述

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

代码如下：

/*** 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().*/typedef struct TreeNode TreeNode;int TreeSize(TreeNode*root){if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);}
//前序遍历：根左右void _preorderTraversal(TreeNode*root,int*arr,int*pi){if(root==NULL){return;}//为什么这里不是传值，而是要传地址呢，因为传值是放到另一块空间，并没有改变本身，也就意味着，从始至终都是从0开始//形参要想改变实参就要传址调用arr[(*pi)++]=root->val;_preorderTraversal(root->left,arr,pi);_preorderTraversal(root->right,arr,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {//求节点个数*returnSize=TreeSize(root);//计算数组大小int*returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_preorderTraversal(root,returnArr,&i);return returnArr;
}

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

在这里插入图片描述

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

代码如下：

/*** 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().*/typedef struct TreeNode TreeNode;int TreeSize(TreeNode*root){if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);}void _inorderTraversal(struct TreeNode*root,int*arr,int*pi){if(root==NULL){return;}_inorderTraversal(root->left,arr,pi);arr[(*pi)++]=root->val;_inorderTraversal(root->right,arr,pi);}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int* returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_inorderTraversal(root,returnArr,&i);return returnArr;
}

二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100
/*** 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().*/typedef struct TreeNode TreeNode;int TreeSize(TreeNode*root){if(root==NULL){return 0;}return 1+TreeSize(root->left)+TreeSize(root->right);}
void _postorderTraversal(struct TreeNode*root,int*arr,int*pi)
{if(root==NULL){return;}_postorderTraversal(root->left,arr,pi);_postorderTraversal(root->right,arr,pi);arr[(*pi)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*returnArr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;_postorderTraversal(root,returnArr,&i);return returnArr;
}

这三道题我们可以感受到只要掌握了怎样遍历二叉树就会变得简单许多

二叉树遍历

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

示例1

abc##de#g##f###
c b e g d f a

思路如下：
在这里插入图片描述

代码如下：

include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTreeNode
{char data;struct BinaryTreeNode*left;struct BinaryTreeNode*right;
}BTNode;
BTNode* BuyNode(char x)
{BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));newnode->data=x;newnode->left=newnode->right=NULL;return newnode;
}
BTNode*CreateNode(char*arr,int*pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode*root=BuyNode(arr[(*pi)++]);root->left=CreateNode(arr, pi);root->right=CreateNode(arr, pi);return root;
}void Inorder(BTNode*root)
{if(root==NULL){return;}Inorder(root->left);printf("%c ",root->data);Inorder(root->right);
}
int main() {char arr[100];scanf(" %s ",arr);int i=0;BTNode*root=CreateNode(arr,&i);Inorder(root);return 0;
}
http://www.lryc.cn/news/420421.html

相关文章：

  • Unity URP 曲面细分学习笔记
  • 每天五分钟深度学习pytorch：训练神经网络模型的基本步骤
  • 【langchain学习】使用缓存优化langchain中的LLM调用性能：内存、SQLite与Redis的对比
  • spring boot 集成EasyExcel
  • 获取对象中第一个存在的值
  • Python学习笔记----集合与字典
  • c# 排序、强转枚举
  • “华为杯”第十六届中国研究生数学建模竞赛-C题：视觉情报信息分析
  • html+css+js网页设计 找法网2个页面（带js）ui还原度百分之90
  • 018 | backtrader回测反转策略
  • 《图解HTTP》全篇目录
  • 基于VS2019（Release_x64）+Qt的软件开发—环境配置
  • 【书生大模型实战营（暑假场）闯关材料】入门岛：第1关 Linux 基础知识
  • 240810-Gradio通过HTML组件打开本地文件+防止网页跳转到about:blank
  • go在linux上安装
  • 算法日记day 35（动归之分割等和子集|最后一块石头的重量2）
  • FPGA使用sv生成虚拟单音数据
  • Linux shell编程：监控进程CPU使用率并使用 perf 抓取高CPU进程信息
  • Linux网络编程的套接字分析（其一，基本知识）
  • 后端Web开发之Maven
  • 前端创新实践：用JavaScript打造网页扫码新体验
  • AWS CLI命令行
  • 领导力培养的底层逻辑
  • 【MATLAB第107期】基于MATLAB的Morris局部敏感性分析模型（无目标函数）
  • Tomcat搭建JSPServlet
  • 32位定点数和32/64位浮点数的二进制生成方法
  • STM32利用arm-dsp库进行FIR低通滤波【详细】
  • Efficient-KAN 源码详解
  • Jlink commander使用方法（附指令大全）
  • Java SpringBoot实现PDF转图片