653_two_sum_iv_input_is_a_bst

653. 两数之和 IV - 输入 BST 简答

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

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 1}
    fmt.Println(findTarget(root, 2)) // false
}

func findTarget(root *TreeNode, k int) bool {
    m := make(map[int]int)
    return preTraverse(root, k, m)
}

// 和 two sum 一样
func preTraverse(root *TreeNode, k int, m map[int]int) bool {
    if root == nil {
        return false
    }

    if _, ok := m[k-root.Val]; ok { // 先序遍历保证了去重
        return true
    }

    m[root.Val]++
    return preTraverse(root.Left, k, m) || preTraverse(root.Right, k, m)
}