二叉树OJ题：挑战与突破

系列文章目录

🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
😍 👋🏼🎉🎊创作不易，欢迎大家留言、点赞加收藏！！！ 🥳😁😍

一、开源网站分享

在开始总结之前，给各位分享一个开源网站：🔗

常见算法的可视化演示

二、在线OJ题

单值二叉树

（1）题目描述

下面是该题的链接🔗

单值二叉树

（2）思路分析

1、递归终止条件：
如果当前节点为空，说明已经遍历到叶子节点的子节点，此时可以认为是单值二叉树的一部分，返回true。

2、节点值判断：
对于当前节点，先判断其是否有左子节点，
如果有，则比较当前节点的值和左子节点的值，
如果不同，说明整棵树不是单值二叉树，直接返回false。
同理，再判断右子节点的值是否与当前节点相同，不同则返回false。

3、递归遍历子树：
如果当前节点的值与其左右子节点的值都相同（或者没有左右子节点），那么继续递归判断当前节点的左子树和右子树是否都是单值二叉树。
只有当左右子树都是单值二叉树时，整棵树才是单值二叉树，所以返回左右子树判断结果的逻辑与（&&）。

（3）代码示例

// 判断给定的二叉树是否为单值二叉树的函数
bool isUnivalTree(struct TreeNode* root) 
{
    // 如果当前节点为空，说明已经遍历到叶子节点的子节点，返回 true
    if(root == NULL)
        return true;
    
    // 如果当前节点有 左子节点，并且当前节点的值 不等于 左子节点的值，说明不是单值二叉树，返回 false
    if(root->left != NULL && root->val != root->left->val)
        return false;

    // 如果当前节点有 右子节点，并且当前节点的值 不等于 右子节点的值，说明不是单值二叉树，返回 false
    if(root->right != NULL && root->val != root->right->val)
        return false;

    // 递归判断当前节点 的左子树和右子树是否都是单值二叉树，只有当左右子树都是单值二叉树时，整棵树才是单值二叉树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

二叉树的最大深度

（1）题目描述

下面是该题的链接🔗

二叉树的最大深度

（2）思路分析

1、递归终止条件：
如果当前节点为空，说明已经遍历到叶子节点的子节点，此时的深度为 0，返回 0。

2、计算子树深度：
对于当前节点，分别递归计算其左子树和右子树的最大深度，存储在LeftHeight和RightHeight变量中。

3、计算当前树深度：
比较左子树和右子树的最大深度，取较大值，然后加 1，即为当前节点为根的树的最大深度。
加 1 是因为要加上当前节点这一层的深度。

（3）代码示例

// 计算给定二叉树的最大深度的函数
int maxDepth(struct TreeNode* root) 
{
    // 如果当前节点为空，说明已经遍历到叶子节点的子节点，返回深度 0
    if(root == NULL)
        return 0;
    
    // 递归计算当前节点的左子树的最大深度
    int LeftHeight = maxDepth(root->left);
    
    // 递归计算当前节点的右子树的最大深度
    int RightHeight = maxDepth(root->right);

    // 比较左子树和右子树的最大深度，取较大值加 1 即为当前节点为根的树的最大深度
    // 加 1 是因为要加上当前节点这一层的深度
    return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}

翻转二叉树

（1）题目描述

下面是该题的链接🔗

翻转二叉树

（2）思路分析

1、递归终止条件：
当遍历到空节点时，直接返回NULL。因为空节点无需翻转，且它是递归的终止条件，防止无限递归。

2、递归过程：
（1）翻转子树：先递归翻转左子树和右子树。这是因为在翻转当前节点的左右子树之前，需要先确保其子树内部已经完成了翻转。
（2）交换子树：将翻转后的右子树赋值给当前节点的左子树，将翻转后的左子树赋值给当前节点的右子树。
这样就完成了当前节点的左右子树交换，实现了局部的翻转。

3、返回结果：
每次递归调用返回当前节点，作为其父节点翻转后的新子节点。最终，根节点的翻转完成，整个二叉树也就完成了翻转。

（3）代码示例

struct TreeNode* invertTree(struct TreeNode* root) 
{
    // 如果当前节点为空，直接返回 NULL，因为空树无需翻转
    if(root == NULL)
        return NULL;
    
    // 递归翻转左子树，并将结果暂存于 LeftTree 指针
    struct TreeNode* LeftTree = invertTree(root->left);
    // 递归翻转右子树，并将结果暂存于 RightTree 指针
    struct TreeNode* RightTree = invertTree(root->right);
    
    // 将翻转后的右子树赋值给当前节点的左子树
    root->left = RightTree;
    // 将翻转后的左子树赋值给当前节点的右子树
    root->right = LeftTree;

    // 返回翻转后的当前节点，作为其父节点翻转后的新子节点
    return root;
}

相同的树

（1）题目描述

下面是该题的链接🔗

相同的树

（2）思路分析

1、递归终止条件：
如果两个节点都为空，说明在当前遍历位置两棵树的结构相同，都是叶子节点的子节点，返回true。
如果一个节点为空 另一个不为空，说明两棵树结构不同，返回false。

2、节点值判断：
如果两个节点都不为空，但它们的值不同，说明两棵树不相同，返回false。

3、递归遍历子树：
如果两个节点的值相同，继续递归判断两棵树的左子树是否相同，并判断右子树是否相同。
只有当左右子树都相同时，两棵树才相同，所以返回左右子树判断结果的逻辑与（&&）。

（3）代码示例

// 判断两棵二叉树是否相同的函数
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    // 如果两个节点都为空，说明当前遍历到的位置在两棵树中都是叶子节点的子节点，返回 true
    if(p == NULL && q == NULL)
        return true;
    // 如果一个节点为空另一个不为空，说明两棵树结构不同，返回 false
    if(p == NULL || q == NULL)
        return false;

    // 如果两个节点的值不同，说明两棵树不相同，返回 false
    if(p->val != q->val)    
        return false;

    // 递归判断两棵树的左子树是否相同，并且右子树是否相同
    // 只有当左右子树都相同时，两棵树才相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

二叉树的前序遍历

（1）题目描述

下面是该题的链接🔗

二叉树的前序遍历

（2）思路分析

1、计算树的大小：
定义TreeSize函数，用于计算二叉树的节点个数。
如果当前节点为空，返回 0；
否则，递归计算左子树和右子树的节点个数，并加上当前节点（1）。

2、前序遍历辅助函数：
定义preorder函数，用于将前序遍历的结果存储到数组中。如果当前节点为空，直接返回。
否则，先访问当前节点，将其值存储到数组中，并将数组下标指针加 1。
然后递归遍历 左子树 和 右子树。

3、前序遍历主函数：
定义preorderTraversal函数，首先调用TreeSize函数计算二叉树的节点个数，即前序遍历结果数组的大小。
调用preorder函数，将遍历结果存储到数组中。
最后返回前序遍历结果的数组。

（3）代码示例

// 计算二叉树节点个数的函数
int TreeSize(struct TreeNode* root)
{
    // 如果当前节点为空，说明已经遍历到叶子节点的子节点，返回 0
    if(root == NULL)
        return 0;
    // 否则，递归计算 左子树 和 右子树 的节点个数，并加上当前节点（1）
    else
        return TreeSize(root->left) + TreeSize(root->right) + 1;
}

// 前序遍历的 辅助函数，用于将遍历结果存储到数组中
void preorder(struct TreeNode* root,int* a,int* pi)
{
    // 如果当前节点为空，直接返回
    if(root == NULL)
        return;
    // 否则，先访问当前节点，将其值存储到数组中
    else
    {
        a[*pi] = root->val;
        // 数组下标指针加 1，指向下一个存储位置
        ++(*pi);
        
        // 递归遍历左子树
        preorder(root->left,a,pi);
        // 递归遍历右子树
        preorder(root->right,a,pi);
    }
}

// 二叉树前序遍历的主函数
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    // 计算二叉树的节点个数，即前序遍历结果数组的大小
    *returnSize = TreeSize(root);
    // 为前序遍历结果数组分配内存
    int* a = (int*)malloc(*returnSize * sizeof(int));
    // 如果内存分配失败，打印错误信息并返回 NULL
    if(a == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    // 初始化数组下标指针为 0
    int i = 0;
    // 调用前序遍历辅助函数，将遍历结果存储到数组 a 中
    preorder(root,a,&i);

    // 返回前序遍历结果数组
    return a;    
}

对称二叉树

（1）题目描述

下面是该题的链接🔗

对称二叉树

（2）思路分析

1、辅助函数：
定义isSameTree函数，用于判断两棵二叉树是否镜像对称。这个函数的逻辑与之前判断两棵树是否相同的函数类似，但递归参数有所不同。
如果两个节点都为空，返回true，表示当前遍历到的位置是对称的。
如果一个节点为空另一个不为空，返回false，表示两棵树不对称。
如果两个节点的值不同，返回false，表示两棵树不对称。
递归判断两棵树的左子树和右子树是否镜像对称。
注意这里的递归参数是p->left和q->right，以及p->right和q->left，这样才能正确比较镜像对称的子树。

2、主函数：
定义isSymmetric函数，首先判断根节点是否为空。如果根节点为空，返回true，因为空树是对称的。
调用isSameTree函数，判断根节点的左子树和右子树是否镜像对称。
如果左子树和右子树镜像对称，则整棵树是对称的，返回true；否则返回false。

（3）代码示例

// 判断两棵二叉树是否镜像对称的辅助函数
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    // 如果两个节点都为空，说明当前遍历到的位置在两棵树中都是对称的叶子节点的子节点，返回 true
    if(p == NULL && q == NULL)
        return true;
    // 如果一个节点为空另一个不为空，说明两棵树不对称，返回 false
    if(p == NULL || q == NULL)
        return false;

    // 如果两个节点的值不同，说明两棵树不对称，返回 false
    if(p->val != q->val)    
        return false;

    // 递归判断两棵树的左子树和右子树是否镜像对称
    // 注意这里的递归参数，要比较的是 p 的左子树和 q 的右子树，以及 p 的右子树和 q 的左子树
    return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
}

// 判断一棵二叉树是否对称的函数
bool isSymmetric(struct TreeNode* root) 
{
    // 如果根节点为空，说明树为空，空树是对称的，返回 true
    if(root == NULL)
        return true;

    // 调用辅助函数，判断根节点的左子树和右子树是否 镜像对称
    return isSameTree(root->left,root->right);    
}

另一颗树的子树

（1）题目描述

下面是该题的链接🔗

另一颗树的子树

（2）思路分析

1、辅助函数：
定义isSameTree函数，用于判断两棵二叉树是否相同。这个函数的逻辑与之前判断两棵树是否相同的函数相同。
如果两个节点都为空，返回true，表示当前遍历到的位置是相同的。
如果一个节点为空另一个不为空，返回false，表示两棵树结构不同。
如果两个节点的值不同，返回false，表示两棵树不相同。
递归判断两棵树的左子树和右子树是否相同。只有当左右子树都相同时，两棵树才相同。

2、主函数：
定义isSubtree函数，首先判断主树的当前节点是否为空。
如果为空，说明已经遍历完主树的当前分支，没有找到子树，返回false。
调用isSameTree函数，判断当前主树节点和子树根节点是否相同。
如果相同，说明可能找到了子树，返回true。
如果当前节点不是子树，继续在主树的左子树和右子树中递归查找子树。只要有一边找到子树就返回true。

（3）代码示例

// 判断两棵二叉树是否相同的辅助函数
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    // 如果两个节点都为空，说明当前遍历到的位置在两棵树中都是叶子节点的子节点，返回 true
    if(p == NULL && q == NULL)
        return true;
    // 如果一个节点为空另一个不为空，说明两棵树结构不同，返回 false
    if(p == NULL || q == NULL)
        return false;

    // 如果两个节点的值不同，说明两棵树不相同，返回 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) 
{
    // 如果主树的当前节点为空，说明已经遍历完主树的当前分支，没有找到子树，返回 false
    if(root == NULL)
        return false;

    // 如果当前主树节点和子树根节点相同，说明可能找到了子树，调用辅助函数判断是否完全相同
    if(isSameTree(root,subRoot) == true)
        return true;

    // 如果当前节点不是子树，继续在主树的左子树和右子树中递归查找子树
    // 只要有一边找到子树就返回 true
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

二叉树遍历

（1）题目描述

下面是该题的链接🔗

二叉树遍历

（2）思路分析

1、创建二叉树：
定义CreateTree函数，根据先序遍历序列创建二叉树。函数参数包括字符数组 a 和递归指针 pi。
如果当前字符为 #，说明当前节点为空，递归指针后移，返回NULL。
否则，创建一个新的节点，设置节点值为当前字符，递归指针后移。
递归创建左子树和右子树。

2、中序遍历：
定义InOrder函数，进行中序遍历。如果当前节点为空，直接返回。
（1）递归遍历左子树，访问当前节点，
（2）打印节点值，
（3）递归遍历右子树。

3、主函数：
读取输入的先序遍历序列，存储在字符数组 a 中。
调用CreateTree函数根据输入序列创建二叉树。
调用InOrder函数进行中序遍历并打印结果。

（3）代码示例

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
struct TreeNode
{
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
    char val;               // 节点值，这里用字符表示
};

// 根据先序遍历序列（用 '#' 表示空节点）创建二叉树的函数
struct TreeNode* CreateTree(char* a,int* pi)
{
    // 如果当前字符为 '#'，说明当前节点为空，递归指针后移，返回 NULL
    if(a[*pi] == '#')
    {
        ++(*pi);
        return NULL;
    }
    // 如果当前字符为不是 '#'，说明当前节点不为空
    else
    {   
        // 创建根节点
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        // 如果内存分配失败，打印错误信息并返回 NULL
        if (root == NULL) 
        {
            perror("malloc fail");
            return NULL;
        }

        // 设置节点值为当前字符，递归指针后移
        root->val = a[*pi];
        ++(*pi);

        // 递归创建左子树
        root->left = CreateTree(a,pi);
        // 递归创建右子树
        root->right = CreateTree(a,pi);
        // 返回根节点
        return root;
    }
}

// 中序遍历二叉树的函数
void InOrder(struct TreeNode* root)
{
    // 如果当前节点为空，直接返回
    if (root == NULL) 
        return;
    
    // 递归遍历左子树
    InOrder(root->left);
    // 访问当前节点，打印节点值
    printf("%c ",root->val);
    // 递归遍历右子树
    InOrder(root->right);
}

// 主函数
int main()
{
    // 定义字符数组用于存储输入的先序遍历序列
    char a[100];
    // 读取输入的先序遍历序列
    scanf("%s",a);

    // 初始化递归指针为 0
    int i = 0;
    // 调用 CreateTree 函数根据输入序列创建二叉树
    struct TreeNode* root = CreateTree(a,&i);
  
    // 调用 InOrder 函数进行中序遍历并打印结果
    InOrder(root);

    return 0;
}

END

每天都在学习的路上！
On The Way Of Learning