【Leetcode】相同的树、对称二叉树、另一颗树的子树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Leetcode】相同的树、对称二叉树、另一颗树的子树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

💡相同的树

题目描述

思路：

代码：

💡对称二叉树

题目描述

思路：

代码：

💡另一棵树的子树

题目描述

思路：

代码：

💡总结

【Leetcode】相同的树、对称二叉树、另一颗树的子树,数据结构,leetcode,算法,数据结构

💡相同的树

题目描述

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

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

【Leetcode】相同的树、对称二叉树、另一颗树的子树,数据结构,leetcode,算法,数据结构

思路：

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

代码：

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
}