题解 | #树的子结构#
树的子结构
http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88
class Solution {
public:
bool isSubTree(TreeNode* pRoot1, TreeNode* pRoot2){
if (!pRoot2){
return true;
}
if (!pRoot1){
return false;
}
if (pRoot1->val == pRoot2->val){
return isSubTree(pRoot1->left, pRoot2->left) && isSubTree(pRoot1->right, pRoot2->right);
}
return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot1 || !pRoot2){
return false;
}
if (isSubTree(pRoot1, pRoot2) && isSubTree(pRoot1, pRoot2)){
return true;
}
return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
}
};
递归方法:主要是要考虑好退出条件
1.空树不为任意树的子结构,所以pRoot2空时返回false
2.pRoot1为空时,必定返回false
3.当前节点相等时,递归判断左右子树
4.当前节点不等时,保留完整pRoot2结构,从pRoot1的左右子树中递归寻找