网站缩略图制作,宁波商城网站建设,西安网站设计 牛人网络,建设专业网站排名前言 本篇博客我们来仔细说一下二叉树二叉树的一些OJ题目 请看完上一篇#xff1a;数据结构-二叉树-CSDN博客 #x1f493; 个人主页#xff1a;普通young man-CSDN博客 ⏩ 文章专栏#xff1a;LeetCode_普通young man的博客-CSDN博客 若有问题 评论区见#x1f4dd; 数据结构-二叉树-CSDN博客 个人主页普通young man-CSDN博客 ⏩ 文章专栏LeetCode_普通young man的博客-CSDN博客 若有问题 评论区见 欢迎大家点赞收藏⭐文章 目录
图解
题目及其代码
题目一
编辑
题目二
编辑
题目三
编辑
题目四
题目五
编辑
题目六 图解 题目及其代码
题目一
965. 单值二叉树 - 力扣LeetCodehttps://leetcode.cn/problems/univalued-binary-tree/description/ 如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。 只有给定的树是单值二叉树时才返回 true否则返回 false。 示例 1 输入[1,1,1,1,1,null,1]
输出true示例 2 输入[2,2,2,5,2]
输出false提示 给定树的节点数范围是 [1, 100]。每个节点的值都是整数范围为 [0, 99] 。 // 函数声明检查给定的二叉树根节点是否代表一个单值树
bool isUnivalTree(struct TreeNode* root) {// 如果根节点为空也认为它是单值树空树可以视为所有节点值都相同的情况if (root NULL)return true;// 检查左子树如果存在左子节点并且其值不等于根节点的值则返回falseif (root-left root-left-val ! root-val)return false;// 检查右子树如果存在右子节点并且其值不等于根节点的值则返回falseif (root-right root-right-val ! root-val)return false;// 递归检查左子树和右子树是否也都是单值树// 只有当左右子树都是单值树并且它们的值与当前根节点的值相同时整个树才是单值树return isUnivalTree(root-left) isUnivalTree(root-right);
} 题目二
100. 相同的树 - 力扣LeetCodehttps://leetcode.cn/problems/same-tree/description/ 给你两棵二叉树的根节点 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 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//判断是否都为NULL注意两个为NULL也算相等if (p NULL q NULL)return true;//判断一个为NULL一个不为NULLif(p NULL || q NULL )return false;//判断接节点的值是否相等这边主要判断不相等这样可以排除更多可能if(p-val ! q-val)return false;//返回如果都为真就相等如果有一个为假就不相等return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
} 题目三
101. 对称二叉树 - 力扣LeetCodehttps://leetcode.cn/problems/symmetric-tree/description/ 给你一个二叉树的根节点 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 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//判断是否都为NULL注意两个为NULL也算相等if (p NULL q NULL)return true;//判断一个为NULL一个不为NULLif(p NULL || q NULL )return false;//判断接节点的值是否相等这边主要判断不相等这样可以排除更多可能if(p-val ! q-val)return false;//返回如果都为真就相等如果有一个为假就不相等return isSameTree(p-left,q-right) isSameTree(p-right,q-left);
} 题目四
144. 二叉树的前序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 94. 二叉树的中序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-inorder-traversal/description/
145. 二叉树的后序遍历 - 力扣LeetCodehttps://leetcode.cn/problems/binary-tree-postorder-traversal/description/ 这个三个OJ写法差不多只需要改变一点就能实现
// 前序遍历二叉树的辅助函数
// 参数:
// - root: 当前正在访问的二叉树节点指针
// - arr: 用于存储遍历结果的整型数组
// - i: 指向当前数组索引的指针用于在遍历时追踪下一个存储位置
void Tree_preorder(struct TreeNode* root, int* arr, int* i){// 如果当前节点为空则直接返回结束当前递归路径if(root NULL)return;// 将当前节点的值存入数组并递增索引i使用指针解引用后加法避免了直接传值的问题arr[(*i)] root-val;// 递归遍历左子树Tree_preorder(root-left, arr, i);// 递归遍历右子树Tree_preorder(root-right, arr, i);
}// 计算二叉树的节点总数
// 参数:
// - root: 二叉树的根节点指针
// 返回值:
// - 树的节点总数空树返回0
int Treesize(struct TreeNode* root){// 递归终止条件如果树为空返回0return root NULL ? 0 : // 否则节点总数等于左子树节点数 右子树节点数 1根节点Treesize(root-left) Treesize(root-right) 1;
}// 主要函数执行二叉树的前序遍历并返回结果数组
// 参数:
// - root: 二叉树的根节点指针
// - returnSize: 输出参数返回数组的实际元素数量
// 返回值:
// - 存储前序遍历结果的数组指针
int* preorderTraversal(struct TreeNode* root, int* returnSize) {// 首先计算二叉树的总节点数用于动态数组的分配*returnSize Treesize(root); // 通过树的节点个数确定数组大小// 根据节点总数动态分配内存给数组arrint *arr (int*)malloc(sizeof(int)*(*returnSize));// 初始化索引变量i为0用于记录数组中的当前位置int i 0;// 调用前序遍历的辅助函数填充数组Tree_preorder(root, arr, i);// 完成遍历后返回存储了前序遍历结果的数组return arr;
} 题目五
572. 另一棵树的子树 - 力扣LeetCodehttps://leetcode.cn/problems/subtree-of-another-tree/ 给你两棵二叉树 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;* };*/
// 函数判断两棵二叉树是否相同
// 参数p 和 q 分别表示两棵树的根节点
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {// 如果两棵树的当前节点都为NULL说明已遍历完且两者结构相同返回trueif (p NULL q NULL)return true;// 如果只有一个节点为NULL说明两棵树结构不同返回falseif (p NULL || q NULL)return false;// 检查当前节点的值是否相等如果不等则两棵树不相同返回falseif (p-val ! q-val)return false;// 递归检查左右子树是否也相同只有都相同才返回truereturn isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}// 函数判断一棵树中是否存在和另一棵树相同的子树
// 参数root 是大树的根节点subRoot 是要查找的子树的根节点
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {// 如果大树的当前节点为空说明没有找到子树返回falseif (root NULL) {return false;}// 如果大树的当前节点与子树的根节点值相等// 进一步检查以当前节点为根的子树是否与subRoot相同if (root-val subRoot-val isSameTree(root, subRoot)) {// 如果相同返回truereturn true;}// 在当前节点的左子树和右子树中递归查找子树subRoot// 使用逻辑或操作只要一边存在匹配即返回truereturn isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
} 题目六
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId60tqId29483rp1ru/activity/ojqru/ta/tsing-kaoyan/question-ranking 描述 编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。 输入描述 输入包括1行字符串长度不超过100。 输出描述 可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。 示例1 输入 abc##de#g##f### 输出 c b e g d f a #include stdio.h
#include stdlib.h// 更改基本数据类型名称为DataType以增强代码可读性
typedef char DataType;// 定义二叉树节点结构体包含节点值data及左右子节点指针
typedef struct TreeNode {DataType data; // 节点存储的数据原代码中的val改为data以增强理解struct TreeNode* left; // 左子节点指针struct TreeNode* right; // 右子节点指针
} TreeNode;// 创建二叉树的函数接收字符串表示的树结构和当前字符索引指针
// 字符串中#表示空节点其他字符表示节点值
TreeNode* CreateTree(char* p, int* pi) {// 当遇到 #表示当前节点为空索引加一后返回NULLif (p[*pi] #) {(*pi);return NULL;}// 动态分配新节点内存检查是否分配成功TreeNode* root (TreeNode*)malloc(sizeof(TreeNode));if (!root) { // 内存分配失败处理fprintf(stderr, Memory allocation failed\n);exit(EXIT_FAILURE); // 程序退出}// 初始化节点值并递增索引指向下一个字符root-data p[(*pi)];// 递归创建左子树和右子树root-left CreateTree(p, pi);root-right CreateTree(p, pi);return root; // 返回当前创建的节点
}// 中序遍历二叉树的函数按照“左-根-右”的顺序访问每个节点
void InOrder(TreeNode* root) {if (root NULL) return; // 遇到空节点直接返回结束递归InOrder(root-left); // 先遍历左子树printf(%c , root-data); // 打印当前节点值InOrder(root-right); // 最后遍历右子树
}int main() {char arr[100]; // 用于存储输入的二叉树字符串表示int i 0; // 索引变量用于追踪字符串中的当前字符位置// 从用户输入中读取二叉树的字符串表示scanf(%s, arr);// 根据输入字符串创建二叉树TreeNode* root CreateTree(arr, i);// 对创建的二叉树进行中序遍历并打印节点值InOrder(root);return 0; // 程序正常结束
}
