题解 | #树的子结构#

 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function HasSubtree(pRoot1, pRoot2)//这个函数的作用是：判断以pRoot1为根的树所能形成的所有子结构是否包含pRoot2这样的结构。
// 重点就在这里，所谓的所有子结构包括了：
//     以pRoot1为根的所有树；
//     以pRoot1的左节点为根的所有树，以pRoot1的右节点为根的所有树；
//     以pRoot1的左节点的左节点为根的所有树。。。。。。

    // 1，上帝给了我一个函数，这个函数可以判断以pRoot1为根的树所能形成的所有子结构是否包含pRoot2这样的结构。
{
    // 2，但是不能把它直接还给上帝，不然上帝会生气的。至少要做点最简单情况的处理。
    // 特殊处理：空树
    if(pRoot1 === null || pRoot2 === null){
        return false;
    }
    return isSubtree(pRoot1, pRoot2) // 特殊处理：判断以pRoot1为根的所有树是否包含pRoot2这样的树结构
    // 3，最简单的情况处理完，剩下的用上帝写好的函数处理。
    || HasSubtree(pRoot1.left, pRoot2)   //判断以pRoot1的左子树为根的树所能形成的所有子结构是否包含pRoot2这样的树结构
    || HasSubtree(pRoot1.right, pRoot2); //判断以pRoot1的右子树为根的树所能形成的所有子结构是否包含pRoot2这样的树结构
}

function isSubtree(rootA, rootB){// 这个函数的作用是：判断以A为根节点的所有树是否包含树B这样的结构
    // 1，上帝给了我一个函数，这个函数可以判断以A为根节点的所有树是否包含树B这样的结构。
    // 2，但是不能把它直接还给上帝，不然上帝会生气的。至少要做点最简单情况的处理。
    // 特殊处理：
    // 如果rootB为空，证明rootB已经比较完了，当前树A完整地包含了树B。或者说，任何树都包含了空树这样的结构。
    if(rootB === null){
        return true;
    }
    // 如果rootB不为空，但是rootA为空，说明当前树A没有完整地包含树B。或者说，空树不会包含除了空树外的任何树结构。
    else if(rootA === null){
        return false;
    }
    // 如果二者都不为空，就判断val值，值不相同所以不包含
    else if(rootA.val !== rootB.val){
        return false;
    }
    // 3，最简单的情况处理完，剩下的用上帝写好的函数处理。
    return isSubtree(rootA.left, rootB.left) // 判断以A的左子树为根节点的所有树是否包含B的左子树这样的结构
    && isSubtree(rootA.right, rootB.right);  // 判断以A的右子树为根节点的所有树是否包含B的右子树这样的结构
}

module.exports = {
    HasSubtree : HasSubtree
};