【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。

🌈个人主页：主页链接

🌈算法专栏：专栏链接

我会一直往里填充内容哒！

🌈LeetCode专栏：专栏链接

目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出

🌈代码仓库：Gitee链接

🌈点击关注=收获更多优质内容🌈

呜呜呜呜今天被蓝桥杯爆杀了

题目:100. 相同的树

题解:

代码实现:

题目:572. 另一棵树的子树

题解:

代码实现:

题目:236. 二叉树的最近公共祖先

题解:

代码实现:

完结撒花：

题目:100. 相同的树

题解:

这题算是简单题，我们依然从最简单的情况来考虑。

如果只有一个节点的时候:怎么判断这两个节点是否相等呢?

首先,先判断其左右根的属性是否相同.

属性的含义是:其是否都有左右根,若没有,则没有是否没有同一边

其次再进行判断,这个点的值是否相等.

这样就完成了对一个节点的判断,我们只需要一一比较这两棵树的节点是否相同,就能比较出来了

代码实现:


struct TreeNode {
     int val;
     struct TreeNode *left;
      struct TreeNode *right;
 };


#include<iostream>
using namespace std;
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));

}

题目:572. 另一棵树的子树

题解:

这题与上面那题大同小异,寻找一棵树的子树,

我们可以把问题拆分为:这颗树的子树与subroot是否相等,这样就又变成了,上面那个问题.

如何判断两棵树是否相等.(只是多了一个遍历每颗子树的过程)

废话不多说,我们直接来看代码吧

代码实现:

#include<iostream>
using namespace std;
struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(!p&&!q)return true;
    if(!p||!q)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);
}

题目:236. 二叉树的最近公共祖先

题解:

依旧先看看基础情况,若访问的这个节点与p或者q相同,则说明找到了他,则直接返回就可以了.

之后再判断是否两边都找到了

若两边都找到了,则说明left与right最近的公共节点就是当前访问的这个节点root.

若只有一边找到了,则说明这其中一个节点可能做为另一个节点的根,则直接返回根节点(left,right)即可

之后再加入递归的元素,依次遍历访问每棵树的左节点称为left

依次遍历访问每棵树的右节点称为right

若出现以上三种情况.则不为空.

代码实现:

#include<iostream>
using namespace std;
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
 };
 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL||root->val==p->val||root->val==q->val)return root;
        TreeNode* left=lowestCommonAncestor(root->left,  p, q);
        TreeNode*right=lowestCommonAncestor(root->right,p,q);
        if(left!=NULL&&right!=NULL)return root;
        if(right==NULL)return left;
        if(left==NULL)return right;
        return NULL;
    }
};