题目

二叉树A中是否包含二叉树B

思路

轮询A找到与B根节点相同的点，然后 递归查询B的左、右子树是否与A中对应结点相同 见代码注释

代码

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) :val(x),left(nullptr),right(nullptr){ } }; class Solution { public: bool HasSubtree (TreeNode* pRoot1, TreeNode* pRoot2){ bool re = false; // 判断 A、B都必须不为空才可比较 if (pRoot1 != nullptr && pRoot2 != nullptr){ // 如果root1中的结点与root2中根节点相同则进行子左右子树对比 if (pRoot1->val == pRoot2->val){ re = Tree1HasTree2(pRoot1,pRoot2); } // 如果根结点不同，那么递归查询左子树中与root2相同的结点 if(!re) re = HasSubtree(pRoot1->left,pRoot2); if(!re) // 如果所有左子树都和root2中根节点都不同，那么递归查询右子树中与root2根结点相同的结点 re = HasSubtree(pRoot1->right,pRoot2); } return re; } private: bool Tree1HasTree2 (TreeNode* pRoot1, TreeNode* pRoot2){ // 如果root2先轮询完毕或者root1和root2同时轮询完毕，则root2为root1的子树 if(pRoot2 == nullptr) return true; // 如果root1先轮询完，则说明root1内没有root2子树 if(pRoot1 == nullptr) return false; // 如果两个结点不同，则返回false if(pRoot1->val != pRoot2->val) return false; // 如果 roo1和root2中所有对应的左右子树都一样，则返回true return Tree1HasTree2(pRoot1->left,pRoot2->left)&& Tree1HasTree2(pRoot1->right,pRoot2->right); } };