数据结构初阶-二叉树的应用

1.单值二叉树

题目链接：https://leetcode.cn/problems/univalued-binary-tree/description/

题目思路：我们把根结点与左孩子和右孩子进行比较，只有左右子树都是单值二叉树的时候才为单值二叉树。但是我们需要先返回的是false，最后再返回左子树&&右子树的结果。所以代码如下：

 typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) 
{
    if(root==NULL)
    {
        //如果全为空的情况下，没有存储任何值也就是单值二叉树
        return true;
    }
    if(root->left && root->val != root->left->val)
    {
        //当左孩子不存在时我们仍然返回的是true
        //root->left是判断是否左子树为空的
        return false;
    }
    if(root->right && root->val !=root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2.相同的树

题目链接：https://leetcode.cn/problems/same-tree/description/

题目思路：如果p、q一者为空另一者为非空，则为false，我们使用前序遍历的方法，最终返回p的左子树和q的左子树的返回值&&p的右子树和q的右子树的返回值。

typedef struct TreeNode TreeNode;
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);
}

我们主要是返回的是false,如果我们在第三个if条件下p->val==q->val return true;这样我们不确定之后的树中是否还是相同的情况，只有我们最终比较到两者都为空才行。

*3对称二叉树（扩展）

题目链接：https://leetcode.cn/problems/symmetric-tree/description/

题目思路：由于我们发现这个给出的函数只有一个参数，但是我们需要比较的是左子树的左结点和右子树的右结点的返回值&&左子树的右结点和右子树的左结点的返回值，所以我们需要另外一个函数来判断，思路要把单值二叉树和相同的树进行整合，最终能得到以下代码：

bool panduan(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 panduan(p->left,q->right) && panduan(p->right,q->left);
    }
    return false;
 }
bool isSymmetric(struct TreeNode* root) 
{
    if(root==NULL)
    {
        return true;
    }
    return panduan(root,root);
}

4.另一棵树的子树

题目链接：https://leetcode.cn/problems/subtree-of-another-tree/description/

题目思路：我们把第二题的代码全部放入题目后，然后每次都调用这个函数，先递归左子树再递归右子树，并返回二者或的结果，代码如下：

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

5.二叉树的前序遍历

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

题目思路：返回值为int*，我们需要返回数组，数组还必须手动malloc。我们需要先求出二叉树结点的个数，这个函数我们之前写过，就不需要讲解了；然后我们需要malloc结点个数的数据，最后前序遍历，最终代码如下：

typedef struct TreeNode TreeNode;
 //求二叉树结点个数
 int TreeSize(TreeNode* root)
 {
    if(root==NULL)
    {
        return 0;
    }
    return 1+TreeSize(root->left)+TreeSize(root->right);
 }
 //前序遍历
 void PreOrder(TreeNode* root,int* arr,int* pi)
 {
    if(root==NULL)
    {
        return ;
    }
    arr[(*pi)++]=root->val;
    PreOrder(root->left,arr,pi);
    PreOrder(root->right,arr,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //我们需要自己求出结点个数
    *returnSize=TreeSize(root);
    int* arr=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    //我们需要不断递增下标，所以要传址操作
    PreOrder(root,arr,&i);
    return arr;
}

拓展练习，题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

和https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

6.二叉树的构建及遍历

该题目难度较难，所以有兴趣的可以去看

题目链接：https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

题目思路：首先我们需要根据数组来创建二叉树，之前我们是手动来创建二叉树的，所以我们没有注意这个问题，这个题目就可以锻炼我们创建二叉树的技巧。如何根据数组来创建二叉树？只要不为#我们就创建这个结点，第一个不为#的就是根结点，所以我们需要一个创建结点的函数，之前我们写过，所以很简单，然后我们用传址操作来得到每一个结点，先进行根结点的创建，再是左孩子，最后右孩子，最终代码如下：

#include <stdio.h>
//定义结点
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
//创建结点
BTNode* buyNode(char ch)
{
    BTNode* node=(BTNode*)malloc(sizeof(BTNode));
    node->data=ch;
    node->left=node->right=NULL;
    return node;
}
//创建二叉树
BTNode* createTree(char* arr,int* pi)
{
    if(arr[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root=buyNode(arr[*pi]);
    ++(*pi);
    root->left=createTree(arr,pi);
    root->right=createTree(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=createTree(arr, &i);
    InOrder(root);
    return 0;
}

7.总结和下节预告

这些题目难度都还行，只要虚心学习，不断在自己思考的情况下，这些题目还是很容易的。喜欢的可以一键三连哦，下节将讲解：排序1 。