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

淡淡的烟草味﹌ 2024-03-30 11:39 63阅读 0赞

>  作者：一个喜欢猫咪的的程序员
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![d62cffa130804aa38f2fcab2ecf3359f.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> 965. 单值二叉树 
> 
>  100. 相同的树
> 
> 572. 另一棵树的子树
> 
> --------------------

## 965. 单值二叉树 ##

[965. 单值二叉树![icon-default.png_t_M85B][]https://leetcode.cn/problems/univalued-binary-tree/][965. _icon-default.png_t_M85B_https_leetcode.cn_problems_univalued-binary-tree]

题目描述：

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

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

--------------------

示例：

![8cd4a916506243c48d16e7ed2c15b4a1.png][]

--------------------

思路：

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

![85059e21ce02407aa68d0d91a9f52f4d.gif][]

--------------------

代码实现：

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][icon-default.png_t_M85B]https://leetcode.cn/problems/same-tree/][100. _icon-default.png_t_M85B_icon-default.png_t_M85B_https_leetcode.cn_problems_same-tree]

题目描述：

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

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

--------------------

示例：

![a616db58af2441828f3a6b1a9c8b865f.png][]

--------------------

思路：

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

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

--------------------

代码实现：

--------------------

## 572. 另一棵树的子树 ##

[572. 另一棵树的子树![icon-default.png?t=M85B][icon-default.png_t_M85B]https://leetcode.cn/problems/subtree-of-another-tree/][572. _icon-default.png_t_M85B_icon-default.png_t_M85B_https_leetcode.cn_problems_subtree-of-another-tree]

题目描述：

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

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

--------------------

示例：

![ffd3019793014115b7a9cde98350f732.png][]

![0efced153e4e4c2baf381a28a7cfd652.png][]

--------------------

思路：

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

**当树相等时，直接放回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);
    }

[d62cffa130804aa38f2fcab2ecf3359f.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d108fb352939430ead6dd5359becb5f6.jpeg
[icon-default.png_t_M85B]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b5d3da3f7fdc457ead6e74e6f80b7696.png
[965. _icon-default.png_t_M85B_https_leetcode.cn_problems_univalued-binary-tree]: https://leetcode.cn/problems/univalued-binary-tree/
[8cd4a916506243c48d16e7ed2c15b4a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0259d328277646ba8d6c0db91a95f1e0.png
[85059e21ce02407aa68d0d91a9f52f4d.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ddb4e9c6ba794304929abc6d90863b65.gif
[100. _icon-default.png_t_M85B_icon-default.png_t_M85B_https_leetcode.cn_problems_same-tree]: https://leetcode.cn/problems/same-tree/
[a616db58af2441828f3a6b1a9c8b865f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/195044f9242540edbfda0ff3af3ed955.png
[572. _icon-default.png_t_M85B_icon-default.png_t_M85B_https_leetcode.cn_problems_subtree-of-another-tree]: https://leetcode.cn/problems/subtree-of-another-tree/
[ffd3019793014115b7a9cde98350f732.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/efa9c14119cb446196c4d15681c9a919.png
[0efced153e4e4c2baf381a28a7cfd652.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f96477608fab43209ffb5ea2b2015466.png