【数据结构】二叉树基础OJ

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树基础OJ。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1. 单值二叉树

2. 检查两颗树是否相同

3. 对称二叉树

4. 二叉树的前序遍历

5. 二叉树的中序遍历

6. 二叉树的后序遍历

7. 另一颗树的子树

8. 二叉树的结构及遍历


世界上没有不劳而获的东西!


1. 单值二叉树

链接:力扣

代码1

/**
 * 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的条件比较多,所以,返回不相等的条件少】【代码1】(2)遍历,和根的值进行比较

注意:(1)在OJ题中尽量不要定义静态变量和全局变量

2. 检查两颗树是否相同

链接:力扣

代码

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

思想:递归;分治

3. 对称二叉树

链接:力扣

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q)
{
    //
    if (p == NULL && q == NULL)
    {
        return true;
    }
    //其中一个为空
    if (p == NULL || q == NULL)
    {
        return false;
    }
    return p->val == q->val && _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
}

bool isSymmetric(struct TreeNode* root)
{
    if (root == NULL)
    {
        return true;
    }
    return _isSymmetric(root->left, root->right);

}

思想:首先,判断树的左子树和右子树是否相等;然后,判断左子树的左子树和右子树的右子树以及左子树的右子树和右子树的左子树是否相等,以及重复这个操作

4. 二叉树的前序遍历

链接:力扣

代码

/**
 * 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().
 //意思是返回值可以被malloc,假设由调用者释放
 */
//首先确定二叉树的节点个数
int BinaryTreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : (BinaryTreeSize(root->left)+BinaryTreeSize(root->right) + 1);
}

int* preorder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    a[*pi] = root->val;
    (*pi)++;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    //定义的是数组的指针,因为定义的如果是数组,出了这个函数,就被销毁了
    int size = BinaryTreeSize(root);//j节点个数
    int* a = (int*)malloc(sizeof(int) * size);//定义数组
    if (a == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    *returnSize = size;
    //前序遍历,并把结果,给数组,
    int i = 0;
    preorder(root,a, &i);
    return a;
}

思想:首先,我们可以非常容易地想到前序遍历的,把之前学到过的前序遍历的printf,改成数组的赋值。看题意,我们需要定义一个数组的指针和二叉树的节点个数,然后尽可以调用前序遍历的函数,进行解决。

注意:returnSize 这个代表的是数组的大小,这个函数,相当于输出型参数,returnSize,外面定义了,但是没有值,需要我们对齐进行赋值。【这里应该用指针,因为形参的改变并不影响实参】

5. 二叉树的中序遍历

链接:力扣

代码

/**
 * 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 BinaryTreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1);
}


void inorder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    inorder(root->left, a, pi);
    a[*pi] = root->val;
    (*pi)++;
    inorder(root->right, a, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = BinaryTreeSize(root);
    *returnSize = size;
    int* a = (int*)malloc(sizeof(int) * size);
    if (a == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    int i = 0;
    inorder(root, a, &i);
    return a;
}

6. 二叉树的后序遍历

链接:力扣

代码

/**
 * 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 BinaryTreeSize(struct TreeNode* root)
{
   return root == NULL ? 0 : (BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1);
}

void postorder(struct TreeNode* root, int* a, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    postorder(root->left, a, pi);
    postorder(root->right, a, pi);
    a[*pi] = root->val;
    (*pi)++;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = BinaryTreeSize(root);
   *returnSize = size;
   int* a = (int*)malloc(sizeof(int) * size);
   int i = 0;
   postorder(root, a, &i);
   return a;
}

7. 另一颗树的子树

链接:力扣

代码

/**
 * 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;
    }
    return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

思想:分治,根中是否有和subRoot相等+左子树中是否有和subRoot相等的部分+左子树中是否有和subRoot相等的部分。

注意:主函数中,我们可能会漏掉if这个条件语句,如果不写这个代码,root->left,就会出现问题。

8. 二叉树的结构及遍历

链接:牛客

代码

#include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTreeNode
{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
//先构建一个二叉树【前序遍历】
 BTNode* CreatTree(char* a, int* pi)
 {
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    //先构建根
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = a[*pi];
    (*pi)++;
    //再构建左子树和右子树
    root->left = CreatTree(a, pi);
    root->right = CreatTree(a, pi);
    return root;
 }

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

int main()
{
    char a[100];
    scanf("%s", a);
    int i = 0;
    BTNode* tree = CreatTree(a, &i);
    InOrder(tree);
    free(tree);
    tree = NULL;
    return 0;
}

思想:先序遍历的思想的字符串,建立二叉树【遇到'#',就返回NULL】,然后再中序遍历的思想进行打印。文章来源地址https://www.toymoban.com/news/detail-568398.html

到了这里,关于【数据结构】二叉树基础OJ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】_8.二叉树OJ

    目录 1. 题目1:检查两棵树是否相同  2. 题目2:判断一棵树是否为另一棵树的子树 3. 题目3:翻转二叉树 4. 题目4:判断一棵树是否为平衡二叉树 5. 题目5:判断一棵树是否为对称二叉树 6. 题目6:二叉树的层序遍历 7. 题目7:二叉树的遍历 8. 题目8:二叉树的最近公共祖先 9.

    2024年02月12日
    浏览(36)
  • 数据结构:二叉树(初阶)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下二叉树方面的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!   C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个  人  主  页 :stackY、 目录  ​编辑 前言:

    2024年02月07日
    浏览(37)
  • 二叉树经典OJ题——【数据结构】

    W...Y的主页  😊 代码仓库分享 💕  今天我们来进行二叉树的OJ练习,就是利用二叉树的前序、中序、后续以及晨序遍历的特性进行OJ训练。话不多说,来看我们的第一道题。 【leetcode 965.单值二叉树】 OJ链接  如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二

    2024年02月07日
    浏览(46)
  • 【数据结构初阶】树,二叉树

    让我们开始二叉树之前先复习回顾下之前学习的知识 1.1树的概念 树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点, 根节

    2024年02月04日
    浏览(33)
  • 【数据结构初阶】二叉树(2)

    1.1二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个

    2024年02月04日
    浏览(44)
  • 【数据结构初阶】二叉树(1)

    让我们开始二叉树之前先复习回顾下之前学习的知识 1.1树的概念 树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点, 根节

    2024年02月04日
    浏览(36)
  • 数据结构初阶--二叉树的链式结构

    目录 一.二叉树链式结构的概念 二.二叉树链式结构的功能实现 2.1.链式二叉树的定义 2.2.链式二叉树的构建 2.3.链式二叉树的遍历 2.3.1.先序遍历 2.3.2.中序遍历 2.3.3.后序遍历 2.3.4.层序遍历 2.4.链式二叉树的求二叉树的结点数量 法一:计数法 法二:分治法 2.5.链式二叉树的求二

    2024年02月12日
    浏览(43)
  • 数据结构:链式二叉树初阶

    目录 一.链式二叉树的逻辑结构 1.链式二叉树的结点结构体定义 2.链式二叉树逻辑结构 二.链式二叉树的遍历算法 1.前序遍历 2.中序遍历 3.后序遍历  4.层序遍历(二叉树非递归遍历算法) 层序遍历概念: 层序遍历算法实现思路:  层序遍历代码实现: 三.链式二叉树遍历算法的运用

    2024年02月02日
    浏览(45)
  • 【数据结构】二叉树OJ题(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年03月17日
    浏览(45)
  • 【LeetCode】【数据结构】二叉树必刷OJ题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 【LeetCode】226.翻转二叉树 【LeetCode】100.相同的树 【LeetCode】5.对称二叉树 【LeetCode】9.另一颗树的子树

    2024年02月08日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包