[leetcode]653. Two Sum IV - Input is a BST

栏目: 编程工具 · 发布时间: 5年前

内容简介:Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.Example 1:Input:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:

5

/ 3 6

/   2 4 7

Target = 9

Output: True

Example 2:

Input:

5

/ 3 6

/   2 4 7

Target = 28

Output: False

之前想到全部为结点加上parent,然后求它们的前驱后继,但这样时间不够。

然后直接通过中序遍历,将BST 变成数组,二分求值了。

var findTarget = function(root, k) {
    var array = []
    toArray(root, array)
    var low = 0, high = array.length -1
   
    while(low < high){
        var ret = array[low] + array[high]
        var diff = ret - k;
        if(diff === 0){
            return true
        }else if(diff > 0){//值比较大
            high--
        }else {
            low++
        }
    }
    return false
    
};
function toArray(root, array){
   root.left && toArray(root.left, array)
   array[array.length ] = root.val;
   root.right && toArray(root.right, array)
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Scalability Rules

Scalability Rules

Martin L. Abbott、Michael T. Fisher / Addison-Wesley Professional / 2011-5-15 / USD 29.99

"Once again, Abbott and Fisher provide a book that I'll be giving to our engineers. It's an essential read for anyone dealing with scaling an online business." --Chris Lalonde, VP, Technical Operatio......一起来看看 《Scalability Rules》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具