572. Subtree of Another Tree

题干简述：

给我们两个二叉树的根节点，判断 subRoot 是否是 root 的子树。

解题思路

在讲正确的解题思路之前，先看一下我一开始的错误答案：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    if (!root && !subRoot) {
        return true;
    }
    if ((!root && subRoot) || (root && !subRoot)) {
        return false;
    }
    let res = false;
    if (root.val === subRoot.val) {
        res = isSubtree(root.left, subRoot.left) && isSubtree(root.right, subRoot.right);
    } else {
        res = isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    return res;
};

这里的思路很简单，利用递归的思路，从上到下，判断 root 根节点和 subRoot 根节点是否相同且有值，如果相同且有值，则判断其左右子树是否相符，当且仅当左右子树相符时，subRoot 才是 root 的子树；如果不相同，则取root 的左右子树分别与 subRoot 重复上述流程，只有有一个子树满足，subRoot 就是 root 的子树。思路很简单，扫一眼也没有什么问题，我自信的提交了。题目示例中给出的两个用例都准确无误，但是当输入为 [1,1] [1] 的时候，却发生了错误。让我们来仔细分析一下。

image-20210714213948719

将输入 [1, 1] [1] 转化成图示，我们可以看到 subRoot 此时无论是和 root 比较，还是和 root 的 leftChild 比较，都是它的子树，为什么我的代码会返回 false呢？

仔细阅读一下代码，上述的代码，在判断 root.val === subRoot.val 后，继续去比较了它俩的子树是否一致，导致了结果的错误。可能有同学会说，那么当 root.val === subRoot.val 时，直接返回 true 不就好了。这样写的问题在于只比较了根节点，而没有比较子树，差之远已。那么让我们梳理一下，为什么会出现这个错误呢？其实，出现这个错误的原因在于我们比较的时候，并没有把 [1,1] 当做一整个树来和 [1] 进行比较，而是拆分成了一个个节点来进行比较。[1,1] 和 [1] 并非相同的树，此时的结果，应该由 root 这里也就是第一个 val 为 1的节点的子树，与 [1] 是否是相同的树来决定，也就是应该走到 isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) 这个或逻辑而非 isSubtree(root.left, subRoot.left) && isSubtree(root.right, subRoot.right); 这个且逻辑中。我们根据这个结论，对于上述的代码稍作修改，就可以得到正确答案了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    if (!root) return false;
    if (isSame(root, subRoot)) {
        return true;
    }
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
};

var isSame = function (n1, n2) {
    if (!n1 && !n2) {
        return true;
    }
    if ((!n1 && n2) || (n1 && !n2)) {
        return false;
    }
    return n1.val === n2.val && isSame(n1.left, n2.left) && isSame(n1.right, n2.right);
}

Q.E.D.

Take it easy