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
};

 

全部评论

相关推荐

预计下个星期就能开奖吧,哪位老哥来给个准信
华孝子爱信等:对接人上周说的是这周
点赞 评论 收藏
分享
勤奋努力的椰子这就开摆:美团骑手在美团工作没毛病
投递美团等公司10个岗位
点赞 评论 收藏
分享
牛客771574427号:恭喜你,华杰
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务