面试算法56：二叉搜索树中两个节点的值之和

题目

给定一棵二叉搜索树和一个值k，请判断该二叉搜索树中是否存在值之和等于k的两个节点。假设二叉搜索树中节点的值均唯一。例如，在如图8.12所示的二叉搜索树中，存在值之和等于12的两个节点（节点5和节点7），但不存在值之和为22的两个节点。

分析1

解决这个问题最直观的思路是利用哈希表保存节点的值。可以采用任意遍历算法遍历输入的二叉搜索树，每遍历到一个节点（节点的值记为v），就在哈希表中查看是否存在值为k-v的节点。如果存在，就表示存在值之和等于k的两个节点。

解1

public class Test {
    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);

        node8.left = node6;
        node8.right = node10;
        node6.left = node5;
        node6.right = node7;
        node10.left = node9;
        node10.right = node11;

        boolean result = findTarget(node8, 12);
        System.out.println(result);
    }

    public static boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (set.contains(k - cur.val)) {
                return true;
            }

            set.add(cur.val);
            cur = cur.right;
        }

        return false;
    }
}