剑指offer--树的子结构（牛客网）

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

代码：

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){if(pRoot2 == nullptr) return false;if(pRoot1 == nullptr) return false;bool flag = isSubtree(pRoot1, pRoot2);if(flag == false)return HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right, pRoot2);else return true;}bool isSubtree(TreeNode* p1, TreeNode* p2){if(p2 == nullptr) return true;if(p1 == nullptr) return false;if(p1->val == p2->val){return isSubtree(p1->left, p2->left) && isSubtree(p1->right, p2->right);}elsereturn false;}
};

1）保证B为空时，返回false

在 HasSubtree 中判断 pRoot2 为空时, 返回false.

而在 isSubtree 中，已经确定 根节点 pRoot2 是非空的，所以后续子节点如果为空，则到达了叶节点，返回true.

2）B为A的子结构不一定在B中的叶节点在A中也全是叶节点。如 [8,8,7,9,2,#,#,#,#,4,7] 与[8,9,2]

所以在isSubtree中判断为"p1->val == p2->val"，而不能为"p1 == p2"（包含了val, left 和 right）.