【Leetcode】相同的树、对称二叉树、另一颗树的子树

P_M_P

修改于 2024-01-19 10:08:08

1110

修改于 2024-01-19 10:08:08

文章被收录于专栏：算法 Leetcode刷题日志 P_M_P学习笔记算法

💡相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路： 这个题目实际上可以分解为许多个相同的子问题，就是检查每一个子树是否相同，然后便可以利用递归的思想来解答。

代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    return true;
    if(p==NULL&&q!=NULL)
    return false;
    if(p!=NULL&&q==NULL)
    return false;

    if(p->val==q->val)
    {
    return isSameTree(p->right,q->right)&&isSameTree(p->left,q->left);
    }
    return false;
}

💡对称二叉树

题目描述

给你一个二叉树的根节点 root ，检查它是否轴对称。

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

思路： 这个题实际上也是判断相同的树，只不过是判断对称轴左边的左子树与对称轴右边的右子树是否相同和判断对称轴左边的右子树与对称轴右边的左子树子树是否相同（也是需要分解称为多个子问题）。

代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    return true;
    if(p==NULL&&q!=NULL)
    return false;
    if(p!=NULL&&q==NULL)
    return false;

    if(p->val==q->val)
    {
    return isSameTree(p->right,q->left)&&isSameTree(p->left,q->right);
    }
    else
    {
        return false;
    }
}
bool isSymmetric(struct TreeNode* root) {
    return isSameTree(root->left,root->right);
}

💡另一棵树的子树

题目描述

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

思路： 这个题目不难，但是有一个坑，就是当遇到值相等时，就很容易直接判断为true，实际上并不能这样判断，然后把图中4对应的左孩子改为4，那么很显然，subRoot此时就不是root的子树，所以当遇到值相等的结点时，仍然需要继续遍历判断。

代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
    return true;
    if(p==NULL&&q!=NULL)
    return false;
    if(p!=NULL&&q==NULL)
    return false;

    if(p->val==q->val)
    {
    return isSameTree(p->right,q->right)&&isSameTree(p->left,q->left);
    }
    else
    {
        return false;
    }
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    return false;
    //if(root->val==subRoot->val)
   // {
    //    if(isSameTree(root,subRoot))          当前根结点的值相等，不代表这两个树相同，要继续遍历，看这个树的子树是否和所给树相同
                                                //比如将root的值该成4
   //     return true;
   // }
    return isSameTree(root,subRoot)
    ||isSubtree(root->left,subRoot)
    ||isSubtree(root->right,subRoot);//有一个为真，就是true
}