牛客网剑指Offer-树篇-JZ26 树的子结构

题目

来源：JZ26 树的子结构
描述
输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
示例1
输入：
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值：
true
示例2
输入：
{1,2,3,4,5},{2,4}
返回值：
true
示例3
输入：
{1,2,3},{3,1}
返回值：
false

解析

官方题解讲得一塌糊涂，关键概念没解释就算了，代码逻辑还非常混乱。这题的难度应该算较难而不是中等，因为有个关键点很难想到。假设两棵树分别为A,B，B为子树，则B为A的子树有如下三种情况：
1.B和A的根节点相同，B为A的子树。
2.B和A的根节点不同，B为A的左子树的子树。
3.B和A的根节点不同，B为A的右子树的子树。
显然，这三种情况都需要递归，但因为第一种情况和后两种是有本质区别的，所以第一种情况就需要单独写一个函数来判断，假设为IsSubtree。由于题目规定空树不是任意树的子树，所以HasSubtree开头就要排除B为空的情况，则这会引入一个关键点：IsSubtree中传入的B树的节点如果为空，则当前的IsSubtree的递归层数至少是两层，该B树节点不可能在第一层，而且前几层一定都是匹配成功的，所以一定要返回true。 下面举例说明：

显然，当递归层中的B树节点为空时，前几层的节点是匹配成功的，所以要返回true。图中总共要处理两次B树节点为空的情况，两次都要返回true，B树才能正确匹配A树。这点确实是比较难的，这点想不到，这题就不可能做对。
关键点解决了，IsSubtree的算法就不难写了：
1.判断B树节点是否空，若空则返回true。
2.判断A树节点是否为空，若空则返回false。
3.此时A树节点和B树节点都不空，判断它们的值是否相等，若不相等则返回false。
4.此时A树节点和B树节点都不空且相等，则递归判断它们的左右子树是否也都相等。
IsSubtree的实现如下：

bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1->val != pRoot2->val)return false;return IsSubtree(pRoot1->left, pRoot2->left) &&IsSubtree(pRoot1->right, pRoot2->right);
}

这个函数是本题的核心，写对了，后面就很简单了：假设主函数为HasSubtree，则算法如下：
1.判断B树或A树的节点是否空，空则返回false（题目规定空树不是任意树的子树）。
2.调用IsSubtree，判断B和A的根节点是否相同且B是否为A的子树，如果是则返回true。
3.此时B和A的根节点不同，递归判断B是否为A的左（右）子树的子树。
完整代码如下：

bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1->val != pRoot2->val)return false;return IsSubtree(pRoot1->left, pRoot2->left) &&IsSubtree(pRoot1->right, pRoot2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot1 || !pRoot2)return false;return IsSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2)|| HasSubtree(pRoot1->right, pRoot2)  ;
}