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


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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>