给定一个二叉搜索树 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

示例 3：

输入: root = [2,1,3], k = 4
输出: true

示例 4：

输入: root = [2,1,3], k = 1
输出: false

示例 5：

输入: root = [2,1,3], k = 3
输出: true

题解

两种解法

遍历整棵树，map 记录每个节点值，判断是否有 2 个节点相加等于 k 值

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} k
  12.  * @return {boolean}
  13.  */
  14. var findTarget = function(root, k) {
  15.     const map = {}
  16.     let flag = false
  17.     const run = node => {
  18.         if (map[k - node.val] !== undefined) {
  19.             flag = true
  20.         } else {
  21.             map[node.val] = true
  22.         }
  23.         if (node.left) run(node.left)
  24.         if (node.right) run(node.right)
  25.     }
  27.     run(root)
  28.     return flag
  29. };

第二种中序遍历二叉树，会得到一个升序的数组，利用 2 个指针得到 2 数之和

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @param {number} k
  12.  * @return {boolean}
  13.  */
  14. var findTarget = function(root, k) {
  15.     const list = []
  17.     const run = node => {
  18.         if (node.left) run(node.left)
  19.         list.push(node.val)
  20.         if (node.right) run(node.right)
  21.     }
  22.     run(root)
  24.     let i = 0
  25.     let j = list.length - 1
  27.     while(i < j) {
  28.         const num = list[i] + list[j]
  29.         if (num === k){
  30.             return true
  31.         }
  32.         if (num > k) {
  33.             j--
  34.         }
  35.         if (num < k) {
  36.             i++
  37.         }
  38.     }
  39.     return false
  40. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。