树的子结构
题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
看的树的题目可以从递归的角度考虑问题
- 先找到树的根结点，如果大树的根结点与小树的根结点相等，则进而判断大叔是否从这个结点开始包含小树
- 如果不相等，则继续递归的看大树的左子树，以及大树的右子树
代码
#include <iostream>
using namespace std;
class Solution {
public:
bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
// 定义一个变量，储存结果
bool result = false;
// 判断边界条件
if (pRoot1 == NULL || pRoot2 == NULL)
return false;
// 如果两个树都不是空树,并且树根的值相等
if (pRoot1->val == pRoot2->val) {
result = DoesTree1HasTree2(pRoot1, pRoot2);
}
// 如果上面发现小树不是大树的子树，则继续看小树是不是大树的左子树的sub tree
if (!result) {
result = HasSubtree(pRoot1->left, pRoot2);
}
if (!result) {
result = HasSubtree(pRoot1->right, pRoot2);
}
return result;
}
private:
// DoesTree1HasTree2这个函数用来判断当两个树的树根相等的时候，其下方的子树是否相等
bool DoesTree1HasTree2(TreeNode *root1, TreeNode *root2) {
bool result;
// 第一次进入此函数的时候，root1的值和root2的值必然是相等的
// root2也一定是非空的
if (root2 == NULL)
return true;
// 如果root2不是空，但是root1已经为空了
// 则说明root2包含了root1没有的元素
// 故小树不是大树的sub tree
if (root1 == NULL)
return false;
// 上面的两个if条件保证了，root1和root2都不是NULL
// 此时比较一下两个结点的数值，如果相等则继续
// 如果不等则说明不是子树，返回false
if (root1->val != root2->val) {
return false;
}
// 如果进行到了这个步骤，则说明前三个if都不成立，即：
// root1不是NULL，root2不是NULL，root1和root2的值相等
// 则继续比较root1和root2的左右子树
// 若都返回真则说明小树是大树的sub tree
result = DoesTree1HasTree2(root1->left, root2->left) && DoesTree1HasTree2(root1->right, root2->right);
return result;
}
};
// 通过HasSubtree函数来找到两个树相同的根结点
// 当找到了相同的根结点之后，用DoesTree1HasTree2函数来对小树和大树深入的比较
2018.10.10
