为了方便说明，先看两个例子。

例子 1

下图是第一个例子，可以看到 B 是 A 的子结构。

第一个例子的判断逻辑是：

  • 比较当前节点值
  • 递归比较左右节点的值
  • 直到遍历完 B 树

例子 2

下图是第二个例子，可以看到 B 也是 A 的子结构。

但是 A 的根节点和 B 的根节点并不相同。因此对于这种情况，需要对 A 树进行递归遍历。如果 B 是 A 的左子树或者右子树的子结构，那么也是可以的。

代码实现

设计两个函数：

  • HasSubtree 的职能：判断 B 是否是 A 的子结构。是，返回 true；否则，尝试 A 的左右子树
  • isSubTree 的职能：封装“判断 B 是否是 A 的子结构”的具体逻辑。 
// 原文地址：https://xxoo521.com/2020-01-13-subtree/
// ac地址：https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function HasSubtree(pRoot1, pRoot2) {
    // 题目约定：约定空树不是任意一个树的子结构
    if (!pRoot1 || !pRoot2) {
        return false;
    }

    return (
        isSubTree(pRoot1, pRoot2) ||
        HasSubtree(pRoot1.left, pRoot2) ||
        HasSubtree(pRoot1.right, pRoot2)
    );
}

function isSubTree(pRoot1, pRoot2) {
    // B树遍历完了，说明B是A的子结构
    if (!pRoot2) {
        return true;
    }
    // A遍历完了，但是B还没有遍历完，那么B肯定不是A的子结构
    if (!pRoot1) {
        return false;
    }

    if (pRoot1.val !== pRoot2.val) {
        return false;
    }

    return (
        isSubTree(pRoot1.left, pRoot2.left) &&
        isSubTree(pRoot1.right, pRoot2.right)
    );
}

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章，获得更好阅读体验