时间戳

首页 > 解决方案 > 无法找出遍历中的逻辑缺陷以检查树中是否有特定的子树

javascript - 无法找出遍历中的逻辑缺陷以检查树中是否有特定的子树

问题描述

我正在尝试解决以下问题：

给定两个非空二叉树 s 和 t，检查树 t 是否与 s 的子树具有完全相同的结构和节点值。s 的子树是由 s 中的一个节点和该节点的所有后代组成的树。树 s 也可以被认为是它自己的子树。

示例 1：

Given tree s:
     3
    / \
   4   5
  / \
 1   2

Given tree t:
   4 
  / \
 1   2

返回真，因为 t 具有与 s 的子树相同的结构和节点值。

示例 2：

Given tree s:
     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:
   4
  / \
 1   2

返回假。

我已经编写了以下代码。我相信它可以正确地比较树，但我没有返回最后一种情况的正确值。

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

const isSubtree = (s, t) => {
    if (!s || !t) return false
    let sameTree = false

const isSubtree = (s, t) => {
    if (!s || !t) return false
    let sameTree = false

    //changed to preOrder, but it does not work for left or right skewed trees
    const dfsPO = c => {
        if (!c) return
        if (c.val === t.val) sameTree = isSameTree(c, t)
        if (c.left) dfsPO(c.left)
        if (c.right) dfsPO(c.right)
        return sameTree
    }
    return sameTree = dfsPO(s)
}

const isSameTree = (c, t) => {
    if (!c && !t) return true
    if (!c || !t) return false
    if (c.val !== t.val) return false
    return isSameTree(c.left, t.left) && isSameTree(c.right, t.right)
}

以下是测试用例：

const tree1 = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2)), new TreeNode(5))
const tree2 = new TreeNode(4, new TreeNode(1), new TreeNode(2))

const tree3 = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(2, new TreeNode(0))), new TreeNode(5))
const tree4 = new TreeNode(4, new TreeNode(1), new TreeNode(2))

const tree5 = new TreeNode(1, new TreeNode(1))
const tree6 = new TreeNode(1)

console.log(isSubtree(tree1, tree2)) //true
console.log(isSubtree(tree3, tree4)) //false
console.log(isSubtree(tree5, tree6)) //true 

//the input for the tree that fails is as follows:

//[1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2]
//[1,null,1,null,1,null,1,null,1,null,1,2]

我需要帮助找出我的逻辑中的缺陷是左倾斜树还是右倾斜树。

标签： javascriptalgorithmrecursiontreedepth-first-search

解决方案

多么有趣的问题！

const empty =
  {}

const tree = (v = null, l = empty, r = empty) =>
  ({ v, l, r })

我们需要两棵树，t1而且t2——

t1:
     3
    / \
   4   5
  / \
 1   2

t2:
   4
  / \
 1   2

我们可以很容易地使用tree-

const t1 =
  tree
    ( 3
    , tree(4, tree(1), tree(2))
    , tree(5)
    )

const t2 =
  tree(4, tree(1), tree(2))

我认为您有正确的想法来测试两棵树是否是equal-

  1. 如果两者t1都t2为空，则没有什么可比较的，返回true
  2. 通过归纳，两者t1和t2都不为空。如果t1xort2为空，则返回 false
  3. 通过归纳，既非t1空也非t2空。如果t1.v匹配t2.v，则递归并比较每个子树
const equal = (t1 = empty, t2 = empty) =>
  t1 === empty && t2 === empty
    ? true                       // 1
: t1 === empty || t2 === empty
    ? false                      // 2
: t1.v === t2.v                  // 3
    && equal(t1.l, t2.l)
    && equal(t2.l, t2.r)

我们可以写isSubTree——

  1. whent为空，s是tifs为空的子树
  2. 经归纳，t不为空。返回equal(t,s)或重复t.l或重复t.r
const isSubTree = (t = empty, s = empty) =>
  t === empty
    ? s === empty          // 1
    : equal(t, s)          // 2
      || isSubTree(t.l, s)
      || isSubTree(t.r, s)

查看实际代码！在您自己的浏览器中验证以下结果 -

const empty =
  {}

const tree = (v = null, l = empty, r = empty) =>
  ({ v, l, r })

const equal = (t1 = empty, t2 = empty) =>
  t1 === empty && t2 === empty
    ? true
: t1 === empty || t2 === empty
    ? false
: t1.v === t2.v
    && equal(t1.l, t2.l)
    && equal(t1.r, t2.r)

const isSubTree = (t = empty, s = empty) =>
  t === empty
    ? s === empty
    : equal(t, s)
      || isSubTree(t.l, s)
      || isSubTree(t.r, s)

const t1 =
  tree
    ( 3
    , tree(4, tree(1), tree(2))
    , tree(5)
    )

const t2 =
  tree(4, tree(1), tree(2))

const t3 =
  tree(4, tree(1), tree(9))

console.log(isSubTree(t1, t2)) // true
console.log(isSubTree(t1, t3)) // false

我希望这种方法向您展示在编写程序时有时少即是多。

布尔逻辑

这个问题是开始学习布尔逻辑的好机会。如果你像我一样，你不喜欢写条件句，比如 -

if (someCondition)
  return true
else
  return false

return someCondition ? true : false

因为someCondition已经是一个布尔值，所以在这两种情况下，写起来都更简单 -

return someCondition

当我们编写时equal，我们看到我们正在返回true并且false在一些代码分支中。但要弄清楚如何清理这些东西并不容易......

const equal = (t1 = empty, t2 = empty) =>
  // can we collapse the explicit bools?
  t1 === empty && t2 === empty
    ? true                       // <-- explicit bool
: t1 === empty || t2 === empty
    ? false                      // <-- explicit bool
: t1.v === t2.v
    && equal(t1.l, t2.l)
    && equal(t1.r, t2.r)

我们不想鲁莽地猜测哪个逻辑是正确的。我们将使用真值表有条不紊地处理这个问题，这样我们就能得到一个可靠的答案——


│ p := (t1 === empty)
│ q := (t2 === empty)

┌───┬───┬──────────┬───────────┬─────────┬──────────┬──────────┬───────────┐
│ p │ q │ p 'and q │ p 'nand q │ p 'or q │ p 'nor q │ p 'xor q │ p 'xnor q │
├───┼───┼──────────┼───────────┼─────────┼──────────┼──────────┼───────────┤
│ 1 │ 1 │    1     │     0     │    1    │    0     │    0     │     1     │
│ 1 │ 0 │    0     │     1     │    1    │    0     │    1     │     0     │
│ 0 │ 1 │    0     │     1     │    1    │    0     │    1     │     0     │
│ 0 │ 0 │    0     │     1     │    0    │    1     │    0     │     1     │
└───┴───┴──────────┴───────────┴─────────┴──────────┴──────────┴───────────┘

参考我们的真值表，我们可以看到and并nor完美地描述了我们的布尔逻辑 -

const equal = (t1 = empty, t2 = empty) =>
                                 //┌───┬───┬┬──────────┬──────────┐
                                 //│ p │ q ││ p 'and q │ p 'nor q │
                                 //├───┼───┼┼──────────┼──────────┤
  t1 === empty && t2 === empty   
    ? true                       //│ 1 │ 1 ││    1     │    0     │

: t1 === empty || t2 === empty   
    ? false                      //│ 1 │ 0 ││    0     │    0     │
                                 //│ 0 │ 1 ││    0     │    0     │

                                 //│ 0 │ 0 ││    0     │    1     │
: t1.v === t2.v                  //└───┴───┴┴──────────┴──────────┘
    && equal(t1.l, t2.l)         
    && equal(t1.r, t2.r)

使用and匹配前两个条件和代码分支；nor匹配我们重复出现的最后一个分支 -

const nor = (x, y) =>
  !(Boolean(x) || Boolean(y))

const equal = (t1 = empty, t2 = empty) =>
                                  //┌───┬───┬┬──────────┬──────────┐
                                  //│ p │ q ││ p 'and q │ p 'nor q │
                                  //├───┼───┼┼──────────┼──────────┤
  nor(t1 === empty, t2 === empty) //│ 0 │ 0 ││    0     │    1     │
    ? t1.v === t2.v
        && equal(t1.l, t2.l)
        && equal(t1.r, t2.r)
    : t1 === empty && t2 === empty//│ 1 │ 0 ││    0     │    0     │
                                  //│ 0 │ 1 ││    0     │    0     │
                                  //│ 1 │ 1 ││    1     │    0     │

或者简单地说——

  1. 如果两棵树都不为空，则如果值匹配且子树相等，则树相等
  2. 通过归纳，至少一棵树是空的。仅当两棵树都为空时，这些树才相等。
const equal = (t1 = empty, t2 = empty) =>
  nor(t1 === empty, t2 === empty)
    ? t1.v === t2.v                 // 1
        && equal(t1.l, t2.l)
        && equal(t1.r, t2.r)
    : t1 === empty && t2 === empty  // 2

注意我们在( )nor之前调用。这是因为我们只想在两棵树都不为空时重复。因为和返回相同的答案和，我们只能通过把它放在第一位来使递归在分支上独占。and&&andnor(p = 1, q = 0)(p = 0, q = 1)nor

推荐阅读