题解 | #树的子结构#

没写出来照抄的 两个递归属实牛 感觉我的思路没问题啊

// /* function TreeNode(x) {
//     this.val = x;
//     this.left = null;
//     this.right = null;
// } */
// function HasSubtree(pRoot1, pRoot2)
// {
//     // write code here
//     let res
//      if(!pRoot1||!pRoot2) return false;
//      if(pRoot1.val===pRoot2.val){
//         if(!pRoot2.left){
//              res=HasSubtree(pRoot1.right,pRoot2.right)
//          }else if(pRoot2.right===null){
//              res=HasSubtree(pRoot1.left,pRoot2.left)
//              return true
//          }else{
//              res=HasSubtree(pRoot1.left,pRoot2.left)&&HasSubtree(pRoot1.right,pRoot2.right)          
//             return true
//          }
//      }else{
//        res=HasSubtree(pRoot1.left,pRoot2)||HasSubtree(pRoot1.right,pRoot2)
//        return false
//      }
// }
// module.exports = {
//     HasSubtree : HasSubtree
// };

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    // 空树做特殊处理
    if(!pRoot1 || !pRoot2){
        return false
    }
    return checkSameTree(pRoot1, pRoot2) // 校验当前节点的左右子树是否相同
    || HasSubtree(pRoot1.left, pRoot2) // 如果不相同，校验pRoot1的左子树
    || HasSubtree(pRoot1.right, pRoot2) // 还不相同校验右子树
}

function checkSameTree(pRoot1, pRoot2){
    // 如果pRoot2不存在，证明pRoot2已经比较完了，且完全相同
    if(!pRoot2){
        return true
    }
    // 如果pRoot2还在，但是pRoot1没了，说明当前子树比pRoot2节点少，所以不相同
    else if(!pRoot1){
        return false
    }
    // 值不相同所以不相同
    else if(pRoot1.val !== pRoot2.val){
        return false
    }
    // 继续校验左右子节点
    return checkSameTree(pRoot1.left, pRoot2.left) && checkSameTree(pRoot1.right, pRoot2.right)
}

module.exports = {
    HasSubtree : HasSubtree
};