653. 两数之和 IV - 输入 BST(JavaScript)
给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
案例 1:
输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 输出: True
案例 2:
输入: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 输出: False
思路:
这道题需要遍历树
设置变量remainders= [ ],将树的节点与k的差值存入其中,若后来遍历的节点的值存在与这个数组,说明有两个节点的和刚好等于k,则返回true
采用队列迭代法的层序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {boolean}
*/
var findTarget = function(root, k) {
if (!root) return false
let queue = [],
remainders = []
queue.push(root)
while (queue.length) {
let curr = queue.shift() // 移除第一个元素并将其返回
if (remainders.indexOf(curr.val) !== -1) return true // 余数数组中包含此节点的值,说明存在两个节点的值之和满足条件,返回成功
remainders.push(k - curr.val)
if (curr.left)
queue.push(curr.left)
if (curr.right)
queue.push(curr.right)
}
return false
};