二叉树OJ题目

在这里插入图片描述

前言

总体上看，二叉树题目方面运用到达递归的情况较多。所以在做题目之前，可以将函数递归部分先行复习。

一.单值二叉树

leetcode题目链接：单值二叉树

在这里插入图片描述

算法逻辑

1. 空节点处理：如果当前节点 root 为空，直接返回 true。因为空树可以被视为单值二叉树，这是递归的终止条件之一。
2. 左子节点检查：如果当前节点有左子节点（root->left 不为空），并且当前节点的值（root->val）与左子节点的值（root->left->val）不同，那么直接返回 false。因为单值二叉树要求所有节点值相同，一旦发现不同值，就可以确定该树不是单值二叉树。
3. 右子节点检查：类似地，如果当前节点有右子节点（root->right 不为空），并且当前节点的值与右子节点的值不同，也直接返回 false。
4. 递归检查子树：如果当前节点的值与左子节点和右子节点的值都相同，那么继续递归检查左子树和右子树。只有当左子树和右子树都是单值二叉树时，整个树才是单值二叉树。因此，函数返回 isUnivalTree(root->left) && isUnivalTree(root->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); 
}

二.相同的树

leetcode题目链接： 相同的树

在这里插入图片描述

算法逻辑

1. 空节点处理： 如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是相同的，这是递归的终止条件之一。 如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能相同。
2. 节点值比较： 如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为两棵相同的树在相同位置上的节点值必须相同。
3. 递归检查子树： 如果两个节点的值相同，继续递归检查它们的左子树和右子树。只有当左子树和右子树都相同（isSameTree(p->left, q->left) && isSameTree(p->right, q->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);

}

三.对称二叉树

leetcode题目链接：对称二叉树

在这里插入图片描述

算法逻辑解析

1. isSameTree 函数 这个函数用于判断两棵二叉树是否镜像对称，而不是简单的相同。其逻辑如下：

• 空节点处理： 如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是镜像对称的。 如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能镜像对称。
• 节点值比较： 如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为镜像对称的树在相同位置上的节点值必须相同。
• 递归检查子树： 如果两个节点的值相同，继续递归检查它们的子树。但与判断两棵树是否相同不同的是，这里需要检查的是 p 的左子树和 q 的右子树是否镜像对称，以及 p 的右子树和 q 的左子树是否镜像对称。因此，递归调用为 isSameTree(p->left, q->right) && isSameTree(p->right, q->left)。

1. isSymmetric 函数 如果根节点为空（root == NULL），返回 true。因为空树是对称的。 否则，调用 isSameTree 函数，传入根节点的左子树和右子树。如果左子树和右子树镜像对称，则整棵树是对称的。

 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->right)&&isSameTree(p->right,q->left);

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

}

四.另一棵树的子树

leetcode题目链接：另一棵树的子树

在这里插入图片描述

算法逻辑解析

1. isSameTree 函数

• 空节点处理： 如果两个节点 p 和 q 都为空（p == NULL && q == NULL），返回 true。因为空树被认为是相同的。 如果其中一个节点为空而另一个不为空（p == NULL || q == NULL），返回 false。因为一个空树和一个非空树不可能相同。
• 节点值比较： 如果两个节点都不为空，但它们的值不同（p->val != q->val），返回 false。因为相同的树在相同位置上的节点值必须相同。
• 递归检查子树： 如果两个节点的值相同，继续递归检查它们的左子树和右子树。只有当左子树和右子树都相同（isSameTree(p->left, q->left) && isSameTree(p->right, q->right)）时，整个树才相同。

1. isSubtree 函数

• 空树处理： 如果 subRoot 为空（subRoot == NULL），返回 true。因为空树被认为是任何树的子树。 如果 root 为空但 subRoot 不为空（root == NULL），返回 false。因为非空树不能是空树的子树。
• 相同树检查： 如果当前 root 和 subRoot 是相同的树（isSameTree(root, subRoot)），直接返回 true。
• 递归检查子树： 如果当前 root 和 subRoot 不相同，继续递归检查 root 的左子树和右子树是否包含 subRoot。即返回 isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot)。

 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(subRoot == NULL)
    return true;
    if(root == NULL)
    return false;
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

五.二叉树的遍历

牛客链接：二叉树的遍历

在这里插入图片描述

1. buyNode 函数

• 功能：创建一个新的二叉树节点。
• 参数：char x，节点存储的数据。
• 返回值：返回一个指向新创建的二叉树节点的指针。
• 逻辑： 使用 malloc 分配内存空间，创建一个新的 BTnode。 将节点的 data 设置为传入的字符 x。 将节点的左右子节点指针初始化为 NULL。 返回新创建的节点指针。

1. creatTree 函数

• 功能：根据先序序列构建二叉树。
• 参数： char* arr：存储先序序列的字符数组。 int* pi：指向当前处理的字符索引的指针。
• 返回值：返回构建好的二叉树的根节点。
• 逻辑： 如果当前字符是 #，表示当前节点为空，递归返回 NULL，并将索引 pi 加1。 如果当前字符不是 #，创建一个新的节点，将当前字符赋值给节点的 data，并将索引 pi 加1。 递归构建左子树和右子树，并将它们分别赋值给当前节点的 left 和 right。 返回当前节点。

1. inorder 函数

• 功能：中序遍历二叉树。
• 参数：BTnode* root，二叉树的根节点。
• 返回值：无。
• 逻辑： 如果当前节点为空，直接返回。 递归遍历左子树。 打印当前节点的数据。 递归遍历右子树。

#include <stdio.h>
#include<stdlib.h>
typedef struct BTnode{
    char data;
    struct BTnode* left;
    struct BTnode* right;
}BTnode;
BTnode* buynode(char x)
{
    BTnode* ptree = (BTnode*)malloc(sizeof(BTnode));
    ptree->data = x;
    ptree->left = ptree->right = NULL;   
    return ptree;
}
BTnode* creatTree(char* arr, int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTnode* root = buynode(arr[*pi]);
     (*pi)++;
    root->left = creatTree(arr,pi);
    root->right = creatTree(arr,pi);
    return root;
}
void inorder(BTnode* root)
{
    if(root == NULL)
    {
        return;
    }
    inorder(root->left);
    printf("%c ",root->data);
    inorder(root->right);
}
int main() {
    char arr[100];
    scanf("%s",arr);
    int i = 0;
    BTnode* root = creatTree(arr,&i);
    inorder(root);
}