LCR143.子结构判断

链接：LCR143.子结构判断
难度：Medium
标签：树、深度优先搜索、二叉树
简介：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。

题解 1 - typescript

• 编辑时间：2021-04-03
• 执行用时：144ms
• 内存消耗：58.2MB
• 编程语言：typescript
• 解法介绍：依次比较所有值。

function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
  if (!A || !B) return false;
  if (A.val === B.val) {
    if (
      (!B.left && !B.right) ||
      (!B.left && A.right?.val === B.right?.val && isSubStructure(A.right, B.right)) ||
      (!B.right && A.left?.val === B.left?.val && isSubStructure(A.left, B.left)) ||
      (A.right?.val === B.right?.val &&
        A.left?.val === B.left?.val &&
        isSubStructure(A.left, B.left) &&
        isSubStructure(A.right, B.right))
    )
      return true;
    return isSubStructure(A.left, B) || isSubStructure(A.right, B);
  } else {
    return isSubStructure(A.left, B) || isSubStructure(A.right, B);
  }
}

题解 2 - typescript

• 编辑时间：2021-04-03
• 执行用时：144ms
• 内存消耗：58.1MB
• 编程语言：typescript
• 解法介绍：利用辅助检测判断是否相等。

const check = (A: TreeNode | null, B: TreeNode | null): boolean => {
  if (!B) return true;
  if (!A) return false;
  return A.val === B.val && check(A.left, B.left) && check(A.right, B.right);
};
function isSubStructure(A: TreeNode | null, B: TreeNode | null): boolean {
  if (!A || !B) return false;
  if (check(A, B)) return true;
  return isSubStructure(A.left, B) || isSubStructure(A.right, B);
}