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

由 发布于

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

给定两个非空的二叉树s和t，请检查树t的子树是否具有完全相同的结构和节点值。的子树是由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

返回false。

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

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]

我需要帮助弄清楚我的逻辑缺陷在哪处是左右倾斜的树。