树的子结构
C++, dfs。
判断B树是不是A树的子结构。
是子结构！！！不是子树！！！
思路：遍历整棵树A，将A树的每个结点和树B的根结点比较
- 如果值相等，从当前结点开始，两棵树同时dfs（前序），对每个结点进行比较：
- 如果两个结点都为空，则说明刚刚经过的路径是完全一样的；
- 如果A的结点为空，而B的结点不为空，说明B在当前路径上比A多，肯定不是子结构；
- 如果A的结点不为空，而B的结点为空，说明A在刚刚走过的路径，如果不算当前结点的话，经过的结点都是一样的，所以说明当前路径是符合子结构的，且无法再继续往下遍历了，所以返回true；
- 如果两个结点都不为空，那么比较值是否相等：
- 如果值相等，那么就得继续看接下来的子节点是否还相等；
- 如果值不相等，说明不是子结构了，返回false。
- 如果值不相等，那么继续dfs看下个结点是否相等。
代码如下：
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot1 || !pRoot2) return false;
if (dfs(pRoot1, pRoot2)) return true;
else return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
}
bool dfs(TreeNode *root1, TreeNode *root2) {
if (!root1 && !root2) return true;
else if (!root1 && root2) return false;
else if (root1 && !root2) return true;
else {
if (root1->val == root2->val)
return dfs(root1->left, root2->left) && dfs(root1->right, root2->right);
else return false;
}
}
};
