“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

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

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
复制代码

示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
复制代码

提示:

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

深度优先搜索 + 哈希表

我们可以使用深度优先搜索的方式遍历整棵树，用哈希表记录遍历过的节点的值。

对于一个值为 x 的节点，我们检查哈希表中是否存在 k−x 即可。如果存在对应的元素，那么我们就可以在该树上找到两个节点的和为 k；否则，我们将 x 放入到哈希表中。

如果遍历完整棵树都不存在对应的元素，那么该树上不存在两个和为 k 的节点。

var findTarget = function(root, k) {
	const set = new Set();
	const helper = (root, k) => {
		if (!root) {
			return false;
		}
		if (set.has(k - root.val)) {
			return true;
		}
		set.add(root.val);
		return helper(root.left, k) || helper(root.right, k);
	}
	return helper(root, k);
};
复制代码

迭代 + 中序遍历 + 双指针

我们对于每个指针新建一个栈。初始，我们让左指针移动到树的最左端点，并将路径保存在栈中，接下来我们可以依据栈来 O(1) 地计算出左指针的下一个位置。右指针也是同理。

计算下一个位置时，我们首先将位于栈顶的当前节点从栈中弹出，此时首先判断当前节点是否存在右子节点，如果存在，那么我们将右子节点的最左子树加入到栈中；否则我们就完成了当前层的遍历，无需进一步修改栈的内容，直接回溯到上一层即可。

var findTarget = function(root, k) {
    const getLeft = (stack) => {
        const root = stack.pop();
        let node = root.right;
        while (node) {
            stack.push(node);
            node = node.left;
        }
        return root;
    }

    const getRight = (stack) => {
        const root = stack.pop();
        let node = root.left;
        while (node) {
            stack.push(node);
            node = node.right;
        }
        return root;
    };

    let left = root, right = root;
    const leftStack = [];
    const rightStack = [];
    leftStack.push(left);
    while (left.left) {
        leftStack.push(left.left);
        left = left.left;
    }
    rightStack.push(right);
    while (right.right) {
        rightStack.push(right.right);
        right = right.right;
    }
    while (left !== right) {
        if (left.val + right.val === k) {
            return true;
        }
        if (left.val + right.val < k) {
            left = getLeft(leftStack);
        } else {
            right = getRight(rightStack);
        }
    }
    return false;
}
复制代码