Desicription
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
|
class { private: bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot2 == nullptr) { return true; } else if(pRoot1 == nullptr) { return false; } else if(pRoot1->val != pRoot2->val) { return false; } return IsSubtree(pRoot1->left, pRoot2->left) && IsSubtree(pRoot1->right, pRoot2->right); } public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if(pRoot1 == nullptr || pRoot2 == nullptr) { return false; } bool result = false; if(pRoot1->val == pRoot2->val) { result = IsSubtree(pRoot1, pRoot2); } if(!result) { result = IsSubtree(pRoot1->left, pRoot2); } if(!result) { result = IsSubtree(pRoot1->right, pRoot2); } return result; } };
|
近期评论