[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)
}

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

查看所有标签

猜你喜欢:

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

智能革命

智能革命

李彦宏 等 / 中信出版集团 / 2017-5-1 / 68.00元

人类历史上的历次技术革命,都带来了人类感知和认知能力的不断提升,从而使人类知道更多,做到更多,体验更多。以此为标准,李彦宏在本书中将人工智能定义为堪比任何一次技术革命的伟大变革,并且明确提出,在技术与人的关系上,智能革命不同于前几次技术革命,不是人去适应机器,而是机器主动来学习和适应人类,并同人类一起学习和创新这个世界。“人工智能”正式写入2017年政府工作报告,折射出未来人工智能产业在我国经济发......一起来看看 《智能革命》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

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

HEX CMYK 互转工具