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