LeetCode之Two Sum IV - Input is a

问题：
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的解法差不多，不过需要在其中加入树的遍历，深度优先遍历和广度优先遍历都可以。把遍历到的值存入到map中，如果在后面能够找到与map中的值相加等于target的值就返回true，否则遍历结束后返回false。

具体实现：

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

有问题随时沟通

具体代码实现可以参考Github