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

Question

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

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

示例1:

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

Given tree t:
   4 
  / \
 1   2

返回 true，因为 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]

我需要帮助找出左偏或右偏树的逻辑缺陷在哪里。

Answer 1

多么有趣的问题!

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

我们可以使用树轻松编写这些 -

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

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

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

1. 如果t1和t2都为空，则没有什么可以比较，返回true
2. 根据归纳，t1 和 t2 都不为空。如果t1 xor t2 为空，则返回 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. 当t为空时，如果s为空，则s是t的子树
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

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

---

---

bool 逻辑

这道题是开始学习 bool 逻辑的好机会。如果你像我一样，你不喜欢写这样的条件语句 -

if (someCondition)
  return true
else
  return false

return someCondition ? true : false

由于 someCondition 已经是一个 bool 值，因此在这两种情况下都更容易编写 -

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 完美地描述了我们的 bool 逻辑 -

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)   

使用和匹配前两个条件和代码分支； 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

注意，我们在 and 之前调用 nor (&&)。这是因为我们只想在两棵树都不为空时重复。因为 and 和 nor 对于 (p = 1, q = 0) 和 (p = 0, q = 1)，我们只能通过将 nor 分支放在前面来使递归独占。