侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 170 篇文章
  • 累计创建 27 个标签
  • 累计收到 226 条评论

目 录CONTENT

文章目录

树的子结构

神奇的程序员
2022-06-30 / 0 评论 / 9 点赞 / 979 阅读 / 1,848 字 正在检测是否收录...

前言

给定两颗二叉树A和B,如何判断B是不是A的子结构,本文将分享一个方案用来解决此问题,欢迎各位感兴趣的开发者阅读本文。

思路分析

在我的数据结构与算法实现系列文章——实现二叉搜索树中,我们知道了二叉树最多只能有两个子节点:左子节点、右子节点。那么,在本题中要判断是否包含,可以分为两步来实现:

  • 在树A中找到和树B的根节点的值一样的节点R

    • 如果树A的节点与树B的根结点相同,则执行进一步的判断(比对两棵树的子结构)得出比对结果
    • 如果得出的结果为false,分别递归树A的左子节点与右子节点跟树B进行比对,直至任意一棵树的叶子节点
  • 判断树A中以R为根节点的子树是否包含和树B一样的结构

    • 如果树B为null则代表树A中包含树B,返回true
    • 如果树A为null则代表树A中不包含树B,返回false
    • 如果比对的两个节点不等,则代表当前A的子树中不包含树B结构,返回false
    • 否则,继续执行递归,直至任意一棵树的叶子节点

image-20220630222011000

实现代码

通过上个章节的分析,我们已经得出了具体的思路,接下来,我们就将思路转换为代码,如下所示:

  • 实现主函数,判断B是否为A的子结构:
    • 递归树A将其与树B的节点进行比对,找到相同的节点再做进一步的比对
export function TreeSubstructure(
  treeA: BinaryTreeNode | null | undefined,
  treeB: BinaryTreeNode | null | undefined
): boolean {
  let result = false;
  if (treeA != null && treeB != null) {
    // 两个节点相同
    if (treeA.key === treeB.key) {
      // 判断树A中是否包含树B
      result = treeAHaveTreeB(treeA, treeB);
    }

    // 继续寻找左子树与右子树
    if (!result) {
      result = TreeSubstructure(treeA?.left, treeB);
    }
    if (!result) {
      result = TreeSubstructure(treeA?.right, treeB);
    }
  }
  return result;
}
  • 实现进一步的比对函数,判断树A的子节点中是否包含跟树B一样的结构
function treeAHaveTreeB(
  treeA: BinaryTreeNode | null | undefined,
  treeB: BinaryTreeNode | null | undefined
): boolean {
  // 递归到了树B的叶节点,代表该节点存在于树A中
  if (treeB == null) {
    return true;
  }
  // 递归到树A的叶节点,代表该节点不存在于树A中
  if (treeA == null) {
    return false;
  }
  if (treeA.key !== treeB.key) {
    return false;
  }
  // 左子树与右子树都相同
  return (
    treeAHaveTreeB(treeA?.left, treeB?.left) &&
    treeAHaveTreeB(treeA?.right, treeB?.right)
  );
}

注意:上述代码中用到了递归,如果你对其不了解,可以移步我的另一篇文章:递归的理解与实现

代码中还用到了一个自定义类型BinaryTreeNode,具体的类型定义请移步示例代码章节。

测试用例

接下来,我们用思路分析章节中所举的例子来测试下上述函数能否正确执行。

const treeA: BinaryTreeNode = {
  key: 8,
  left: {
    key: 8,
    left: { key: 9 },
    right: { key: 2, left: { key: 4 }, right: { key: 7 } }
  },
  right: { key: 7 }
};

const treeB: BinaryTreeNode = {
  key: 8,
  left: {
    key: 9
  },
  right: {
    key: 2
  }
};

const result = TreeSubstructure(treeA, treeB);
console.log("treeA中包含treeB", result);

image-20220630223617368

示例代码

本文所用代码完整版请移步👇:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
9

评论区