当前位置：个人在线分享 > 二叉树—leetcode

二叉树—leetcode

作者 : admin 本文共6110个字，预计阅读时间需要16分钟 发布时间： 2024-06-10 共1人阅读

前言

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

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

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

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

      若有问题 评论区见📝

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

目录

图解：

题目及其代码

题目一

​编辑

题目二

​编辑

题目三

​编辑

题目四

题目五

​编辑

题目六

图解：

二叉树—leetcode插图

题目及其代码

题目一

965. 单值二叉树 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/univalued-binary-tree/description/

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

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

示例 1：

二叉树—leetcode插图(2)

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

示例 2：

二叉树—leetcode插图(3)

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

提示：

  1. 给定树的节点数范围是 [1, 100]。
  2. 每个节点的值都是整数，范围为 [0, 99] 。
// 函数声明：检查给定的二叉树根节点是否代表一个单值树
bool isUnivalTree(struct TreeNode* root) {
    // 如果根节点为空，也认为它是单值树（空树可以视为所有节点值都相同的情况）
    if (root == NULL)
        return true;

    // 检查左子树：如果存在左子节点，并且其值不等于根节点的值，则返回false
    if (root->left && root->left->val != root->val)
        return false;

    // 检查右子树：如果存在右子节点，并且其值不等于根节点的值，则返回false
    if (root->right && root->right->val != root->val)
        return false;

    // 递归检查左子树和右子树是否也都是单值树
    // 只有当左右子树都是单值树，并且它们的值与当前根节点的值相同时，整个树才是单值树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

二叉树—leetcode插图(4)

二叉树—leetcode插图(5)

题目二

100. 相同的树 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/same-tree/description/

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

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

示例 1：

二叉树—leetcode插图(6)

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

示例 2：

二叉树—leetcode插图(7)

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

示例 3：

二叉树—leetcode插图(8)

输入：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，一个不为NULL
    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);
}

二叉树—leetcode插图(9)

二叉树—leetcode插图(10)

题目三

101. 对称二叉树 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/symmetric-tree/description/

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

示例 1：

二叉树—leetcode插图(11)

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

示例 2：

二叉树—leetcode插图(12)

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

提示：

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

二叉树—leetcode插图(13)

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //判断是否都为NULL，注意：两个为NULL也算相等
    if (p == NULL && q == NULL)
        return true;
    //判断一个为NULL，一个不为NULL
    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);
}

二叉树—leetcode插图(14)

题目四

144. 二叉树的前序遍历 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/binary-tree-preorder-traversal/description/

94. 二叉树的中序遍历 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/binary-tree-inorder-traversal/description/

145. 二叉树的后序遍历 – 力扣（LeetCode）二叉树—leetcode插图(1)http://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){
    // 递归终止条件：如果树为空，返回0
    return root == NULL ? 0 : 
           // 否则，节点总数等于左子树节点数 + 右子树节点数 + 1（根节点）
           Treesize(root->left) + Treesize(root->right) + 1;
}

// 主要函数：执行二叉树的前序遍历并返回结果数组
// 参数:
// - root: 二叉树的根节点指针
// - returnSize: 输出参数，返回数组的实际元素数量
// 返回值:
// - 存储前序遍历结果的数组指针
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 首先，计算二叉树的总节点数，用于动态数组的分配
    *returnSize = Treesize(root); // 通过树的节点个数，确定数组大小
  
    // 根据节点总数动态分配内存给数组arr
    int *arr = (int*)malloc(sizeof(int)*(*returnSize));
    
    // 初始化索引变量i为0，用于记录数组中的当前位置
    int i = 0;
    
    // 调用前序遍历的辅助函数填充数组
    Tree_preorder(root, arr, &i);
    
    // 完成遍历后，返回存储了前序遍历结果的数组
    return arr;
}

 二叉树—leetcode插图(15)

二叉树—leetcode插图(16)

题目五

572. 另一棵树的子树 – 力扣（LeetCode）二叉树—leetcode插图(1)http://leetcode.cn/problems/subtree-of-another-tree/

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

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

示例 1：

二叉树—leetcode插图(17)

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

示例 2：

二叉树—leetcode插图(18)

输入：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

二叉树—leetcode插图(19)

/**
 * 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，说明已遍历完且两者结构相同，返回true
    if (p == NULL && q == NULL)
        return true;
    // 如果只有一个节点为NULL，说明两棵树结构不同，返回false
    if (p == NULL || q == NULL)
        return false;
    // 检查当前节点的值是否相等，如果不等则两棵树不相同，返回false
    if (p->val != q->val)
        return false;
    // 递归检查左右子树是否也相同，只有都相同才返回true
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

// 函数：判断一棵树中是否存在和另一棵树相同的子树
// 参数：root 是大树的根节点，subRoot 是要查找的子树的根节点
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    // 如果大树的当前节点为空，说明没有找到子树，返回false
    if (root == NULL) {
        return false;
    }
    // 如果大树的当前节点与子树的根节点值相等，
    // 进一步检查以当前节点为根的子树是否与subRoot相同
    if (root->val == subRoot->val &&  isSameTree(root, subRoot)) {
        // 如果相同，返回true
        return true;
    }
    // 在当前节点的左子树和右子树中递归查找子树subRoot
    // 使用逻辑或操作，只要一边存在匹配即返回true
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

二叉树—leetcode插图(20)

题目六

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)二叉树—leetcode插图(1)http://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 

二叉树—leetcode插图(21)

#include 
#include 

// 更改基本数据类型名称为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) {
    // 当遇到 '#'，表示当前节点为空，索引加一后返回NULL
    if (p[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    // 动态分配新节点内存，检查是否分配成功
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    if (!root) { // 内存分配失败处理
        fprintf(stderr, "Memory allocation failed
");
        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; // 程序正常结束
}

二叉树—leetcode插图(22)

本站无任何商业行为
个人在线分享 » 二叉树—leetcode
admin

admin 钻石

分享到：

相关推荐

E-->