剑指offer - 树的子结构 - JavaScript

剑指offer - 树的子结构 - JavaScript

题目描述:输入两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:我们约定空树不是任意一个树的子结构)。

题目描述

输入两棵二叉树 A,B,判断 B 是不是 A 的子结构。(ps:我们约定空树不是任意一个树的子结构)。

解法 1: 递归法

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

例子 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

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

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×