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

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

内容简介: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)
}

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

查看所有标签

猜你喜欢:

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

内容创业:内容、分发、赢利新模式

内容创业:内容、分发、赢利新模式

张贵泉、张洵瑒 / 电子工业出版社 / 2018-6 / 49

越来越多的内容平台、行业巨头、资本纷纷加入内容分发的战争中,竞争非常激烈。优质的原创性内容将成为行业中最宝贵的资源。在这样的行业形势下,如何把内容创业做好?如何提高自身竞争力?如何在这场战争中武装自己?是每一位内容创业者都应该认真考虑的问题。 《内容创业:内容、分发、赢利新模式》旨在帮助内容创业者解决这些问题,为想要进入内容行业的创业者出谋划策,手把手教大家如何更好地进行内容创业,获得更高的......一起来看看 《内容创业:内容、分发、赢利新模式》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具