【数据结构】二叉树经典oj题

短命女 2024-04-26 10:58 87阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  1. 单值二叉树
 *  2. 检查两颗树是否相同
 *  3. 对称二叉树
 *  4. 二叉树的前序遍历
 *  5. 另一颗树的子树。
 *  6.二叉树的构建及遍历
 *  7.翻转二叉树：
 *  总结

## 前言 ##

在二叉树的学习中，我们学习了递归的思想，但是还需要刷题来真正弄明白这种思想。希望下面的几道经典oj题对你有所帮助。

## 1. 单值二叉树 ##

[OJ链接][OJ]  
![在这里插入图片描述][665165a8da914e408ac09aaba094c019.png]

**深度优先搜索**

一棵树的所有节点都有相同的值，当且仅当对于树上的每一条边的两个端点，它们都有相同的值（这样根据传递性，所有节点都有相同的值）。

因此，我们可以对树进行一次深度优先搜索。当搜索到节点 x 时，我们检查 x与 x 的每一个子节点之间的边是否满足要求。例如对于左子节点而言，如果其存在并且值与 x 相同，那么我们继续向下搜索该左子节点；如果值与 x不同，那么我们直接返回 False。

bool isUnivalTree(struct TreeNode* root)
    {
        
        if(root==NULL)
        {
        
            return true;
        }
        if(root->left!=NULL&&root->val!=root->left->val)
        {
        
            return false;
        }
         if(root->right!=NULL&&root->val!=root->right->val)
        {
        
            return false;
        }
    
       return  isUnivalTree(root->left)&&isUnivalTree(root->right);
    }

## 2. 检查两颗树是否相同 ##

[OJ链接][OJ 1]  
![在这里插入图片描述][ea10e293e2594469af64fdf07083d474.png]

如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。

如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

## 3. 对称二叉树 ##

[OJ链接][OJ 2]

![在这里插入图片描述][9ad72453b5d84f60aad3b01816a9103c.png]  
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。  
![在这里插入图片描述][125ce4fa9e5844c4967cfbec4ca59c45.png]  
因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

*  它们的两个根结点具有相同的值
 *  每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数，左子树的右子树与右子树的左子树相同，左子树的左子树与右子树的右子树相同，这样就形成了镜面对称。

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

## 4. 二叉树的前序遍历 ##

[OJ链接][OJ 3]  
![在这里插入图片描述][a5591c0426694f1aa700b2bcd02b46fb.png]  
其实这道题就是一个简单的前序遍历，只是把打印换成了将数据存入数组

int TreeSize(struct TreeNode* root)
    {
        
    	/*if (root == NULL)
    	{
    		return;
    	}
    	size++;
    	TreeSize(root->left);
    	TreeSize(root->right);*/
    
    	return root == NULL ? 
    		0 : 
    		TreeSize(root->left) + TreeSize(root->right) + 1;
    }
    
    void preorder(struct TreeNode* root, int* pi,int *a)
    {
        
        if(root==NULL)
        {
        
            return ;
        }
        a[(*pi)++]=root->val;
        preorder(root->left,pi,a);
        preorder(root->right,pi,a);
    }
    int* preorderTraversal(struct TreeNode* root, int* returnSize)
    {
        
        *returnSize=TreeSize(root);
        int *a =(int *)malloc(sizeof(int)*(*returnSize));
        int i=0;
        preorder(root,&i,a);
    
        return a;
    
    }

## 5. 另一颗树的子树。 ##

[OJ链接][OJ 4]  
![在这里插入图片描述][747d26902ea64dd5bd5a5050b3d61679.png]  
这道题目其实和查找二叉树数值为x的那个函数很像，我们只要看每个子树和右边那个树是否相等即可。

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

## 6.二叉树的构建及遍历 ##

[OJ链接][OJ 5]  
![在这里插入图片描述][b875b03565e145e8adf317b10ab74738.png]  
  因为前序遍历的顺序是：**根，左子树，右子树**。所以我们在**读取他**来创建二叉树的时候也是这个顺序，我们先创建根，让根与其左子树和右子树相连，而左子树又可以分为左子树的根与其左子树和右子树相连……以此就构建了递归。这里我们只需要注意最后的结束条件，就是出现\#，就返回NULL。

typedef struct BinaryTreeNode {
        
        char data;
        struct BinaryTreeNode* left;
        struct BinaryTreeNode* right;
    } BTNode;
    
    BTNode *CreatTree(char *a,int *pi)
    {
        
        if(a[*pi]=='#')
        {
        
            (*pi)++;
            return NULL;
        }
        BTNode*node=(BTNode*)malloc(sizeof(BTNode));
        node->data=a[(*pi)++];
        node->left=CreatTree(a, pi);
        node->right=CreatTree(a, pi);
    
        return node;
    }
    
    void Inorder(BTNode*root)
    {
        
        if(root==NULL)
        {
        
            return;
        }
        Inorder(root->left);
        printf("%c ",root->data);
        Inorder(root->right);
    }
    int main() {
        
        char a[100];
        scanf("%s",a);
        int i=0;
        BTNode*root=CreatTree(a,&i);
        Inorder(root);
        return 0;
    }

## 7.翻转二叉树： ##

[**OJ链接**][OJ 6]  
![在这里插入图片描述][f503a2cf92b04ffd9dcac7d8b14df3e4.png]

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，**并从叶子节点先开始翻转**。如果当前遍历到的节点 **root 的左右两棵子树都已经翻转**，那么我们**只需要交换两棵子树的位置**，即可完成以 root 为根节点的整棵子树的翻转。

struct TreeNode* invertTree(struct TreeNode* root)
    {
        
        if(root==NULL)
        {
        
            return NULL;
        }
    
        struct TreeNode* left=invertTree(root->left);
        struct TreeNode* right=invertTree(root->right);
    
        
        root->left=right;
        root->right=left;
    
        return root;
    }

## 总结 ##

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5bee4948b8384977b5c536b5867bf738.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5ea243bc89bd4082bfa046c8910cb444.gif
[OJ]: https://leetcode.cn/problems/univalued-binary-tree/
[665165a8da914e408ac09aaba094c019.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/d753cee1b1c34467b79b13702b5c6e08.png
[OJ 1]: https://leetcode.cn/problems/same-tree/
[ea10e293e2594469af64fdf07083d474.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/9dfe9b2b238a42c3b41d26ba73a1b066.png
[OJ 2]: https://leetcode.cn/problems/symmetric-tree/
[9ad72453b5d84f60aad3b01816a9103c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/09c34765603644c4a598a7fa85b0f8a3.png
[125ce4fa9e5844c4967cfbec4ca59c45.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e5f0723ad1374dac853e5d2031df7a5f.png
[OJ 3]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[a5591c0426694f1aa700b2bcd02b46fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/a4ae539524e749d3a0456ea7d4b45edc.png
[OJ 4]: https://leetcode.cn/problems/subtree-of-another-tree/
[747d26902ea64dd5bd5a5050b3d61679.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5b9d80408a5a48fc8e675b3f0a6b6411.png
[OJ 5]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[b875b03565e145e8adf317b10ab74738.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5e99a103e04f4f068f7f1f487dcb5d96.png
[OJ 6]: https://leetcode.cn/problems/invert-binary-tree/solutions/415160/fan-zhuan-er-cha-shu-by-leetcode-solution/
[f503a2cf92b04ffd9dcac7d8b14df3e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c47228cd0232411eab5384acf597d842.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2025242b15ff496ea9c3bec50c008335.gif