【LeetCode】【数据结构】二叉树必刷OJ题
👀樊梓慕：个人主页
🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》
🌝每一个不曾起舞的日子，都是对生命的辜负
目录
前言
【LeetCode】226.翻转二叉树
【LeetCode】100.相同的树
【LeetCode】5.对称二叉树
【LeetCode】9.另一颗树的子树
前言
在学习完二叉树的基本知识后，博主给大家带来了几道经典的二叉树OJ题，快来试试你对于递归的理解到底如何？
欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码：🌟fanfei_c的仓库🌟
=========================================================================
【LeetCode】226.翻转二叉树
原题链接：🍏226. 翻转二叉树🍏
题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
思路：
我们把复杂问题简单化，先考虑交换左右孩子为：
root->left=right;//假设right为右孩子
root->right=left;//假设left为左孩子
如果利用递归的思想，这里right 和 left最好是翻转后的左右子树的根节点。
那么好了，left 和 right的值如何来？
我们就可以有这样的递归过程：
struct TreeNode* left=invertTree(root->left);
struct TreeNode* right=invertTree(root->right);
代码实现：
//方法1
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;
}
//方法2
struct TreeNode* invertTree(struct TreeNode* root)
{
if(root==NULL)
{
return NULL;
}
struct TreeNode* tmp=root->right;
root->right=root->left;
root->left=tmp;
invertTree(root->left);
invertTree(root->right);
return root;
}
【LeetCode】100.相同的树
原题链接：🍏100. 相同的树🍏
题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路：
以递归的思想思考
先递推到最基础的子问题：
最基础的单个节点是否相同，那么首先如果两个都为空，证明相同返回true；
如果有一个为空，另外一个不为空则不相同返回false；
如果两个节点的值不相同，则返回false；
最后回归到大问题：
如何证明两个树都相同呢？
我们可以从左子树开始依次判断，如果不同就直接返回false，只要过程中有一个函数返回false，那么会导致程序直接结束并返回false；
如果相同就继续判断右子树，如果左右子树都递推到空指针了，那么返回true。
代码实现：
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if(p == NULL && q == NULL)
{
return true;
}
//到达这里时，证明p、q至少有一个不为空
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】5.对称二叉树
原题链接：🍏101. 对称二叉树🍏
题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
思想：
大体思想其实与相同的子树相似， 只不过这次是一棵树，那么我们可以额外构建一个函数，传递两个指针参数（左右孩子指针），当作相同的子树那里的两棵树，并且比较时我们令两个指针的左孩子与右孩子比即可。
代码实现：
bool isSymmetricTree(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 isSymmetricTree(p->left,q->right)&&isSymmetricTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root)
{
return isSymmetricTree(root->left,root->right);
}
【LeetCode】9.另一颗树的子树
原题链接：🍏572. 另一棵树的子树🍏
题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路：
根据题目，我们直到subRoot一定不为空，那么我们就需要判断root是否为空的情况，为空直接返回false即可。
什么时候开始进行判断是否为子树呢？
当root->val与subRoot->val相等时，就进入我们是否为子树的判断，这里的判断直接引用我们写的相同的子树即可。
函数返回值为bool值，我们可以采用下面的方式进行判断（逻辑与、逻辑或的结果是真/假）。
return 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(root==NULL)
{
return false;
}
if(root->val==subRoot->val)
{
if(isSameTree(root,subRoot))
{
return true;
}
}
return isSubtree(root->left,subRoot)
||isSubtree(root->right,subRoot);
}
=========================================================================
如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容
🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏＋关注 ~🌟
=========================================================================
