問題：
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.

方法：
與TwoSum的解法差不多，不過需要在其中加入樹的遍歷，深度優(yōu)先遍歷和廣度優(yōu)先遍歷都可以。把遍歷到的值存入到map中，如果在后面能夠找到與map中的值相加等于target的值就返回true，否則遍歷結(jié)束后返回false。

具體實(shí)現(xiàn)：

class TwoSumIV {
    private val map = mutableMapOf<Int, Int>()
    private var target = 0

    class TreeNode(var `val`: Int = 0) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

    /**
     * Definition for a binary tree node.
     * class TreeNode(var `val`: Int = 0) {
     *     var left: TreeNode? = null
     *     var right: TreeNode? = null
     * }
     */
    fun findTarget(root: TreeNode?, k: Int): Boolean {
        target = k
        return find(root)
    }

    private fun find(root: TreeNode?): Boolean {
        if (root == null) {
            return false
        }
        if (map[root.`val`] != null) {
            return true
        }
        map.put(target - root.`val`, 1)
        return find(root.left) || find(root.right)
    }
}

/**
 *      5
 *     / \
 *    3   6
 *   / \   \
 *  2   4   7
 */
fun main(args: Array<String>) {
    val root = TwoSumIV.TreeNode(5)
    root.left = TwoSumIV.TreeNode(3)
    root.right = TwoSumIV.TreeNode(6)
    (root.left)?.left = TwoSumIV.TreeNode(2)
    (root.left)?.right = TwoSumIV.TreeNode(4)
    (root.right)?.right = TwoSumIV.TreeNode(7)
    val twoSumIV = TwoSumIV()
    val result = twoSumIV.findTarget(root, 15)
    println("result $result")
}

有問題隨時(shí)溝通

具體代碼實(shí)現(xiàn)可以參考Github