两数之和 IV - 输入 BST

题目描述：

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

二叉树的节点个数的范围是 [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105

思路:

时间复杂度：O(n),空间复杂度O(n)

中序遍历之后把数字放入数组，然后遍历数组看符不符合条件

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTarget(root *TreeNode, k int) bool {
    var res []int
    var inorder func(root *TreeNode)
    inorder = func(root *TreeNode){
        if root == nil{
            return 
        }
        inorder(root.Left)
        res = append(res, root.Val)
        inorder(root.Right)
    }
    inorder(root)
    l,r := 0,len(res)-1
    for l<r{
        if res[l]+res[r] == k{
            return true
        }else if res[l]+res[r]<k{
            l++
        }else{
            r--
        }
    }
    return false
}

代码效率：

执行用时：24 ms, 在所有 Go 提交中击败了52.82%的用户
内存消耗：7.2 MB, 在所有 Go 提交中击败了76.06%的用户