653. Two Sum IV - Input is a BST

题干简述：

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

解题思路

本题的重点在于二叉检索树。由于二叉检索树的性质，我们可以对其进行中序遍历，得到一个有序递增的数组。这样，问题就简化为了 167. 两数之和 II - 输入有序数组，求解这个问题，我们可以通过二分法，双指针，或是map 来求解。我下面的题解，采用的是双指针的解法。

使用双指针的时候，我们需要注意的是 while 循环时，如何正确的更新我们的 start 与 end 指针。我们取 start 与 end 指针对应的数组元素求和 sum，sum 相对于 k 值，只会有 3 种情况：

  • sum === k ：此时说明满足要求，return true ，结束；
  • sum > k：此时，由于我们数组的有序性，我们 start 和 end 指向的都是当前循环下数组最小和最大值，在这种情况下，它们的和大于 k，我们就需要缩小这个和，也就是减小最大值；毕竟，最小值已经是最小了，没有办法再减小了。换言之，我们需要将 end 指针向前移动；
  • sum < k：类似于上面的 sum > k 的情况，不过我们需要增大最小值，也就是将 start 向后移动；

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
var findTarget = function(root, k) {
    if (!root) return false;
    const arr = [];
    const inorder = (root) => {
        if (!root) return;
        inorder(root.left);
        arr.push(root.val);
        inorder(root.right);
    };
    inorder(root);
    let start = 0;
    let end = arr.length - 1;
    while (start < end) {
        const sum = arr[start] + arr[end];
        if (sum === k) {
            return true;
        } else if (sum < k) {
            start++;
        } else {
            end--;
        }
    }
    return false;
};

Q.E.D.

Take it easy