【Leetcode】965. 单值二叉树、100. 相同的树、572. 另一棵树的子树-蒲公英云

【Leetcode】965. 单值二叉树、100. 相同的树、572. 另一棵树的子树

作者：一个喜欢猫咪的的程序员

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》

目录

单值二叉树

相同的树

另一棵树的子树

965. 单值二叉树

965. 单值二叉树 icon-default.png_t_M85B https://leetcode.cn/problems/univalued-binary-tree/

题目描述：

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例：

思路：

左右节点都不为NULL，当root跟它的左右节点其中一个不相等时，就不是单值二叉树。当root的左右节点有一个为NULL，只需要比较另外一个不为NULL是否与root相等就可以了。这样递归就可以完成。

代码实现：

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

100. 相同的树

100. 相同的树 icon-default.png?t=M85B https://leetcode.cn/problems/same-tree/

题目描述：

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

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

示例：

思路：

当p和q都不为NULL时，对应的节点相等，就递归他们左右节点继续判断。否则return false。

只有当p和q都为NULL时，return true。

代码实现：

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

572. 另一棵树的子树

572. 另一棵树的子树 icon-default.png?t=M85B https://leetcode.cn/problems/subtree-of-another-tree/

题目描述：

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

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

示例：

思路：

利用上题相同的数的代码作为函数。

当树相等时，直接放回true。否则直接遍历每一个子树，当有一个子树相等时就返回true，否则返回false。

代码实现：

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