算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试 算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 另一棵树的子树，我们先来看题面：
https://leetcode-cn.com/problems/subtree-of-another-tree/
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例
解题
这道题就是在 root 的每个子节点上，判断由该子节点构成的子树是否和 subRoot 这颗树相等。判断两颗树相等需要同时满足三个条件：当前两颗树的根节点值相等；两颗树的左子树相等；两棵树的右子树相等。而判断 一棵树 是否为 另一颗树 的子树只需满足以下条件中的一个：当前两棵树相等；或 一棵树 是 另一颗树 的左子树；或 一棵树 是 另一棵树 的右子树。此题采用递归法求解。
代码语言：javascript复制class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root==NULL||subRoot==NULL)
return false;
if(root->val!=subRoot->val){
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}else{
// return judge(root,subRoot);
return judge(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); // 这是为了应对出现有重复元素出现的情况，比如root: 1 1, subroot:1
}
return false;
}
bool judge(TreeNode* root1, TreeNode* root2){
// 这是用来判断子树的
if(root1==NULL&&root2==NULL) // 两个都为空，说明比对完了，返回true
return true;
if(root1==NULL||root2==NULL) // 其中一个为空，说明一个比完，一个还有，返回false
return false;
// 如果是判断子结构的就用下面这种方式
// if(root2==NULL)
// return true;
// if(root1==NULL) // 此时肯定root2不为null，root1为null，所以false；
// return false;
if(root1->val!=root2->val)
return false;
else
return judge(root1->left,root2->left)&&judge(root1->right, root2->right);
}
};好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
LeetCode1-560题汇总，希望对你有点帮助！
LeetCode刷题实战561：数组拆分 I
LeetCode刷题实战562：矩阵中最长的连续1线段
LeetCode刷题实战563：二叉树的坡度
LeetCode刷题实战564：寻找最近的回文数
LeetCode刷题实战565：数组嵌套
LeetCode刷题实战566：重塑矩阵
LeetCode刷题实战567：字符串的排列
LeetCode刷题实战568：最大休假天数
LeetCode刷题实战569：员工薪水中位数
LeetCode刷题实战570：至少有5名直接下属的经理
LeetCode刷题实战571：给定数字的频率查询中位数
