【LeetCode】【牛客】二叉树刷题

目录

一、相同的树

 二、对称二叉树

 三、二叉树的前序遍历

 四、二叉树的中序遍历

 五、二叉树的后序遍历

六、另一棵树的子树 

 七、二叉树的遍历

描述

输入描述：

输出描述：

---

一、相同的树

给你两棵二叉树的根节点 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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//这里我们的pq结点分别是我们需要判断是否完全相同的二叉树
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//如果我们两棵树都是空树，我们认为这是相同的二叉树
    if(p==NULL&&q==NULL)
    {
        return true;
    }
//经过上面的第一个if判断，再运行到这里时，我们知道两颗树不可能同时为空。
//那么我们再需要判断这两颗树中是否有空树，如果有空树，就不是相同的二叉树
    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);
}

 二、对称二叉树

给你一个二叉树的根节点 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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//这里我们直接调用我们上一题中的判断两个二叉树是否相同的代码，但是需要修改一下指针指向。
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);
}

 三、二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

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

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

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

提示：

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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//这里是我们前序遍历的代码。注意因为我们在不同的递归层次中，不同层次的对i的调整
//都需要同步，所以我们就采用传值调用的方式
void preorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    a[(*i)++]=root->val;
    preorder(root->left,a,i);
    preorder(root->right,a ,i);
}

//这里我们初始化一个数组，并且创建我们指向数组不同位置的指针，然后调用我们上述的方法，并且将我们新生成的数组返回
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    preorder(root, a,returnSize);
    return a;
}

 四、二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

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

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
 

提示：

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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

中序遍历操作只需要对我们上述的前序遍历操作修改一下遍历的先后顺序，以及遍历名称即可完成 

 void inorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    inorder(root->left,a,i);
    a[(*i)++]=root->val;
    inorder(root->right,a ,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    inorder(root, a,returnSize);
    return a;
}

 五、二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

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

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
 

提示：

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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

后序遍历操作只需要对我们上述的中序遍历操作修改一下遍历的先后顺序，以及遍历名称即可完成  

void posorder(struct TreeNode* root, int* a,int* i)
{
    if(root==NULL)
    {
        return;
    }
    posorder(root->left,a,i);
    posorder(root->right,a ,i);
    a[(*i)++]=root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    * returnSize=0;
    int *a=malloc(sizeof(int)*2000);
    posorder(root, a,returnSize);
    return a;
}

六、另一棵树的子树 

给你两棵二叉树 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

来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//这里我们依旧是调用我们第一题中判断两颗二叉树是否相同的代码。
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);
}

//采用先序遍历的方式遍历我们的二叉树，然后对于每一个结点，我们都将判断
//以此结点为根节点的二叉树是否跟我们的子树相同
//注意，这里我们的返回时递归调用我们的左子树和右子树，并且以或的形式返回
//因为我们的左子树和右子树中，只要有一个中存在我们子树，整个递归的结果就应该是true
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if (root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

 七、二叉树的遍历

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

牛客网：二叉树遍历_牛客题霸_牛客网

这道题就是将我们二叉树的实现（C语言数据结构）_wolfwalker的博客-CSDN博客 博文中的部分功能给提取出来。

在上述的博文中，我们的二叉树的创建是指定了字符串，而这道题所需要的是手动输入字符串，我们只需要将我们上述博文中的相关内容摘取出来，然后进行一些输入输出方面的修改，即可完成题目。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    assert(node);

    node->_data = x;
    node->_left = NULL;
    node->_right = NULL;

    return node;
}

BTNode* BinaryTreeCreate(char* a,int* pi)
{

    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode *dst= BuyNode(a[*pi]);
    (*pi)++;

    dst->_left = BinaryTreeCreate(a,pi);
    dst->_right = BinaryTreeCreate(a,pi);
    return dst;
}

void BinaryTreeInOrder(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    BinaryTreeInOrder(root->_left);
    printf("%c ",root->_data);
    BinaryTreeInOrder(root->_right);
}

int main()
{
//因为我们的题目中说我们的数组长度不会超过100，所以我们就创建一个100的数组
//然后采用我们的scanf的函数将我们的输入数据传入
    char a[100]={};
    scanf("%s",a);
    int b=0;
    int *pi=&b;

    BTNode *Btree=BinaryTreeCreate(a, pi);
    BinaryTreeInOrder(Btree);
    return 0;
}