二叉树—leetcode

前言

本篇博客我们来仔细说一下二叉树二叉树的一些OJ题目

请看完上一篇：数据结构-二叉树-CSDN博客

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：LeetCode_普通young man的博客-CSDN博客

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

目录

图解：

题目及其代码

题目一

​编辑

题目二

​编辑

题目三

​编辑

题目四

题目五

​编辑

题目六

---

图解：

题目及其代码

题目一

965. 单值二叉树 - 力扣（LeetCode）https://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. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [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. 相同的树 - 力扣（LeetCode）https://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. 对称二叉树 - 力扣（LeetCode）https://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. 二叉树的前序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

94. 二叉树的中序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

145. 二叉树的后序遍历 - 力扣（LeetCode）https://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. 另一棵树的子树 - 力扣（LeetCode）https://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?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/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; // 程序正常结束
}