正餐---二叉树的OJ题

---

目录???????

前言🍯

1. 检查两颗树是否相同🥇

1.1 思路分析🪙

1.2 代码实现🧰

2. 单值二叉树🌲

2.1 思路分析🔮

2.2 代码实现💈

3. 二叉树的前序遍历🎟?

3.1 思路分析🕰?

3.2 代码实现💸

4. 翻转二叉树🏎?

4.1 思路分析💷

4.2 代码实现🛠?

5. 另一颗树的子树🚂

5.1 思路分析🛡?

5.2 代码实现🎐

?6.二叉树的构建及遍历🚃

7. 对称二叉树🚧

7.1 思路分析🧧

7.2 代码实现📆

8. 判断一颗二叉树是否是平衡二叉树🚦

8.1 思路分析🎁

8.2 代码实现🛍?

课后作业🍭

1.二叉树的后序遍历🩸

2.二叉树的中序遍历💎

?3. 二叉树最大深度🍩

3.1 思路分析

后语🍰

---

前言🍯

Hey,guys!又见面了，还记得上篇博客，我们干了什么吗？没错👍，我们对二叉树和堆排序相关的知识点进行了巩固复习。今天，我们的主要任务就是对递归有更深的理解，可以更好地运用递归的思想。今天主要就是二叉树的oj题。

废话不多说，我们进行今天的学习！！！

---

1. 检查两颗树是否相同🥇

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1.1 思路分析🪙

---

1.2 代码实现🧰

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 isSameTree(p->left,q->left)&&
        isSameTree(p->right,q->right);//2个都相同才返回true
    else//不相同
        return false;    
}

---

2. 单值二叉树🌲

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2.1 思路分析🔮

---

2.2 代码实现💈

 bool isSameNode(struct TreeNode* root,int data)
 {
     if(root==NULL)
         return true;
     if(root->val!=data)
         return false;
     return isSameNode(root->left,data)&&
     isSameNode(root->right,data);//左右都要比较（每个节点都要比较）
 }
bool isUnivalTree(struct TreeNode* root) {
    int data=root->val;
    return isSameNode(root,data);
}

3. 二叉树的前序遍历🎟?

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

3.1 思路分析🕰?

此题需要保存节点，所以需要先获取节点个数，然后进行前序遍历，保存每一个节点值。

这也是为什么要有这道题，前序遍历的实现之前见过了，忘记的小伙伴再去看看吧。

3.2 代码实现💸

 //节点个数 = 左右子树节点个数 + 1
 int BzSize(struct TreeNode* root)
 {
     if(root==NULL)
         return 0;
     return BzSize(root->left)+BzSize(root->right)+1;
 }
 //前序遍历+保存
void ProeOrder(struct TreeNode* root,int* a,int* pi)
{
    if(root)
    {
         a[(*pi)++]=root->val;
         ProeOrder(root->left,a,pi);
         ProeOrder(root->right,a,pi);
    }
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* a,i=0;
    *returnSize=BzSize(root);
    a=(int*)malloc(sizeof(int)*(*returnSize));
    ProeOrder(root,a,&i);
    return a;
}

---

4. 翻转二叉树🏎?

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

4.1 思路分析💷

---

4.2 代码实现🛠?

 void ChangeNode(struct TreeNode* root)
{
    if(root==NULL)
        return;
    struct TreeNode* tmp=root->left;
    root->left=root->right;
    root->right=tmp;
    //每一个节点都要交换
    ChangeNode(root->left);
    ChangeNode(root->right);
}
struct TreeNode* invertTree(struct TreeNode* root) {
    ChangeNode(root);
    return root;
}

---

5. 另一颗树的子树🚂

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

5.1 思路分析🛡?

---

5.2 代码实现🎐

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

bool isSubtree(struct TreeNode* s, struct TreeNode* t){     
    if(s == NULL)
        return false;
    //根相同，判断当前这个树是否和t相同
    if(isSameTree(s, t))
        return true;
    return isSubtree(s->left, t)
            || isSubtree(s->right, t);
}

---

?6.二叉树的构建及遍历🚃

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

#include <stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
    char* val;
    struct TreeNode* left;
    struct TreeNode* right;
}TNode;
//创建二叉树
TNode* CreateTree(char* str,int* pi)
{
    if(str[*pi]!='#'){
         //当前节点非空，则创建当前节点
         TNode* root=(TNode*)malloc(sizeof(TNode));
         root->val=str[(*pi)++];
         //创建左子树
         root->left=CreateTree(str,pi);
         (*pi)++;
         //创建右子树
         root->right=CreateTree(str,pi);
         return root;
    }
    else {
        return NULL;
    }
}
//中序遍历
void InOrder(TNode* root){
    if(root==NULL)
        return;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
int main() {
    char str[101];
    int i=0;
    //读入字符串
    scanf("%s",str);
    //创建二叉树
    TNode* root=CreateTree(str,&i);
    //中序遍历输出
    InOrder(root);
    return 0;
}

---

7. 对称二叉树🚧

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

7.1 思路分析🧧

---

7.2 代码实现📆

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

---

8. 判断一颗二叉树是否是平衡二叉树🚦

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

8.1 思路分析🎁

---

8.2 代码实现🛍?

 int TreeHight(struct TreeNode* root){
     return root==NULL?0:
     fmax(TreeHight(root->left),TreeHight(root->right))+1;
 }
 bool _isBalanced(struct TreeNode* root){
     if(root==NULL)
         return true;
     int h1=TreeHight(root->left);
     int h2=TreeHight(root->right);
     if(abs(h1-h2)>1)
         return false;
     return _isBalanced(root->left)&&
     _isBalanced(root->right);
 }
bool isBalanced(struct TreeNode* root) {
    if(root==NULL)
        return true;
    return _isBalanced(root);
}

---

----课后作业🍭

1.二叉树的后序遍历🩸

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2.二叉树的中序遍历💎

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

?3. 二叉树最大深度🍩

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

3.1 思路分析

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

可以理解就是求高度h

---

后语🍰

本次我们完成了一些二叉树的oj练习题，我也给大家留了一些课后作业，有需要的小伙伴可以自己点击链接去练习，希望今天的题目让大家对递归有了更好的运用！！！

下一篇博客，我们将一起学习排序的相关知识点！请大家多多期待🙏

---

本次的分享到这里就结束了！！！

PS：小江目前只是个新手小白。欢迎大家在评论区讨论哦！有问题也可以讨论的！期待大家的互动！！！

公主/王子殿下，请给我点赞👍+收藏??+关注?（这对我真的很重要！！！）