/* 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 (pRoot1 == nullptr || pRoot2 == nullptr) return false; bool res = false; if (pRoot1->val == pRoot2->val) { res = isPart(pRoot1, pRoot2); } // 如果找不到,就找左子树 if (!res) { res = HasSubtree(pRoot1->left, pRoot2); } // 左子树找不到,就找右子树 if (!res) { res = HasSubtree(pRoot1->right, pRoot2); } return res; } bool isPart(TreeNode* t1, TreeNode* t2) { // 节点值相同才会进入isPart函数,终止条件就是到 t1 或 t2 的叶子节点 if (t2 == nullptr) return true; // 如果 t2 还没有遍历完,t1 却遍历完了。返回false if (t1 == nullptr) return false; if (t1->val != t2->val) return false; return isPart(t1->left, t2->left) && isPart(t1->right, t2->right); } };