无法弄清楚如何解决返回两个总和为二叉树中目标值的值的逻辑缺陷

Question

我正在解决以下问题：

给定一个二叉搜索树和一个目标数，return如果 BST 中存在两个元素并且它们的和等于给定的目标，则为真。

示例 1：输入：

目标 = 9 输出：真

示例 2：输入：

目标 = 28 输出：假

我写了下面的代码：

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 findTarget = (root, k) => {
    const hash = {}
    const values = []
    // let val1, val2 //amended to =>
    let val1 = null
    let val2 = null

    const dfs = (c) => {
        if (!c) return
        values.push(c.val)
        hash[c.val] = c.val
        if (c.left) dfs(c.left)
        if (c.right) dfs(c.right)
    }
    dfs(root)
    for (let v of values) {
        // if (val1 && val2) return true //amended to =>
        if (val1 !== null && val2 !== null) return true
        if (hash[k - v] && !val1) val1 = v
        else if (hash[k - v] && val1) val2 = v
    }
    // return !!(val1 && val2) //amended to =>
    return (val1 !== null && val2 !== null)
}

// These are the test cases:
const tree = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)))
const tree2 = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)))
const tree3 = new TreeNode(2, new TreeNode(0, new TreeNode(-4), new TreeNode(1)), new TreeNode(3))
const tree4 = new TreeNode(0, new TreeNode(-2, null, new TreeNode(-1)), new TreeNode(3, null, new TreeNode(4)))

console.log(findTarget(tree, 9)) //true
console.log(findTarget(tree2, 28)) //false
console.log(findTarget(tree3, -1)) //true
console.log(findTarget(tree4, -2)) //true but I return false

然而，最后一个 return 是错误的，但它应该 return 是正确的，我已经在白板上逐步完成了它应该可以工作。我怀疑当分配给 val1 或 val2 时 0 没有通过 true/false 测试，但我不知道如何使 0 的值应该 return 为真。至少这就是我认为的解决方案，但不确定如何去做，而不是仅仅添加另一个 or 语句来处理这种情况。

Answer 1

搜索相应哈希值时的 for 循环看起来有点可疑，尤其是 robinsax 观察到的 not 运算符的使用。建议简化为...

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 findTarget = (root, k) => {
    const hash = new Map();

    const dfs = (c) => {
        if (!c) return;
        hash.set( c.val, ( hash.get( c.val ) || 0 ) + 1 );
        if (c.left) dfs(c.left);
        if (c.right) dfs(c.right);
    }
    dfs(root);
    
    for ( let v in  [...hash.keys()] ) {
      // Check to see if entry k-v exists.  Also, if v is the same as k-v then
      // ensure that there is more than one v.
      if ( hash.get( k - v ) && ( v == k - v ? 1 < hash.get( v ) : true ) ) {
        return true;
      }
    };

    return false;
}

const tree = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)));
const tree2 = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)));
const tree3 = new TreeNode(2, new TreeNode(0, new TreeNode(-4), new TreeNode(1)), new TreeNode(3));
const tree4 = new TreeNode(0, new TreeNode(-2, null, new TreeNode(-1)), new TreeNode(3, null, new TreeNode(4)));
const tree5 = new TreeNode(1);
const tree6 = new TreeNode(1, new TreeNode(1), new TreeNode(2));

console.log(findTarget(tree, 9)); //true
console.log(findTarget(tree2, 28)); //false
console.log(findTarget(tree3, -1)); //true
console.log(findTarget(tree4, -2)); //true
console.log(findTarget(tree5, 2)); // false because 1 appears once
console.log(findTarget(tree6, 2)); // true because 1 appears twice

编辑添加逻辑以容纳重复节点，以及测试用例 tree5 和 tree6。

希望这对您有所帮助...

Answer 2

表达式 !val1 将是 true，不仅当 val1 是 null 时，而且当它是 0 时。类似的事情发生在 && val2 在接下来的 if 中。同样，您应该将 hash[k - v] 与 undefined 进行比较。因此，当您将 if...else 块替换为：

时，您的代码将得到修复

        if (hash[k - v] !== undefined && val1 === null) val1 = v
        else if (hash[k - v] !== undefined && val1 !== null) val2 = v

或者，在 else 部分保存一张支票：

        if (hash[k - v] !== undefined) {
            if (val1 === null) val1 = v;
            else               val2 = v;
        }

我这里给出另一种算法，不需要先收集hash中的所有值，而是进行两次中序遍历，一次从左到右（即非降序值），和另一个从右到左（即非升序值）。当找到的两个值之和大于目标值时，从右边开始的遍历应该进行一步。否则从左边来的遍历应该走一步。

class TreeNode {
    constructor(val, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    * inorder(first, last) {
        if (this[first]) yield * this[first].inorder(first, last);
        yield this;
        if (this[last]) yield * this[last].inorder(first, last);
    }
    find(k) {
        let asc = this.inorder("left", "right");
        let lo = asc.next();
        let desc = this.inorder("right", "left");
        let hi = desc.next();
        while (lo.value !== hi.value) { // while not the same node
             let sum = lo.value.val + hi.value.val;
             if (sum === k) return true;
             if (sum < k) lo = asc.next();
             else         hi = desc.next();
        }
        return false;
    }
}

const tree = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)))
const tree2 = new TreeNode(5, new TreeNode(3, new TreeNode(2), new TreeNode(4)), new TreeNode(6, null, new TreeNode(7)));
const tree3 = new TreeNode(2, new TreeNode(0, new TreeNode(-4), new TreeNode(1)), new TreeNode(3));
const tree4 = new TreeNode(0, new TreeNode(-2, null, new TreeNode(-1)), new TreeNode(3, null, new TreeNode(4)));
console.log(tree.find(9))   // true
console.log(tree2.find(28)) // false
console.log(tree3.find(-1)) // true
console.log(tree4.find(-2)) // true

无法弄清楚如何解决返回两个总和为二叉树中目标值的值的逻辑缺陷

Can't figure out how to address logic flaw in returning two values that sum to a target value in a Binary Tree

javascript

arrays

algorithm

binary-tree

if-statement