offer2-56

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

示例 1：

输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：

输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

提示：

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

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return doFind(root, root, k);
    }

    private boolean doFind(TreeNode root, TreeNode node, int k) {
        if (node == null) {
            return false;
        }
        if (k - node.val != node.val && isFound(root, k - node.val)) {
            return true;
        } else {
            return doFind(root, node.left, k) || doFind(root, node.right, k);
        }
    }

    private boolean isFound(TreeNode root, int v) {
        if (root == null) {
            return false;
        }

        if (root.val == v) {
            return true;
        } else if (root.val < v) {
            return isFound(root.right, v);
        } else {
            return isFound(root.left, v);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)