题目

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

注意：本题与主站 653 题相同：

解题思路分析

1、递归+哈希辅助；时间复杂度O(n)，空间复杂度O(n)

func findTarget(root *TreeNode, k int) bool {
   if root == nil {
      return false
   }
   m := map[int]int{}
   return dfs(root, k, m)
}

func dfs(node *TreeNode, k int, m map[int]int) bool {
   if node == nil {
      return false
   }
   if _, ok := m[k-node.Val]; ok {
      return true
   }
   m[node.Val] = node.Val
   return dfs(node.Left, k, m) || dfs(node.Right, k, m)
}

2、递归；时间复杂度O(n)，空间复杂度O(log(n))

func findTarget(root *TreeNode, k int) bool {
   return dfs(root, root, k)
}

func dfs(root, searchRoot *TreeNode, k int) bool {
   if root == nil {
      return false
   }
   found := findNode(searchRoot, k-root.Val)
   if found != nil && found != root {
      return true
   }
   return dfs(root.Left, searchRoot, k) ||
      dfs(root.Right, searchRoot, k)
}

func findNode(root *TreeNode, target int) *TreeNode {
   if root == nil {
      return nil
   }
   if root.Val == target {
      return root
   }
   if root.Val < target {
      return findNode(root.Right, target)
   }
   return findNode(root.Left, target)
}

3、迭代；时间复杂度O(n)，空间复杂度O(n)

func findTarget(root *TreeNode, k int) bool {
   if root == nil {
      return false
   }
   m := make(map[int]int)
   queue := make([]*TreeNode, 0)
   queue = append(queue, root)
   for len(queue) > 0 {
      node := queue[len(queue)-1]
      queue = queue[:len(queue)-1]
      if _, ok := m[k-node.Val]; ok {
         return true
      }
      if node.Left != nil {
         queue = append(queue, node.Left)
      }
      if node.Right != nil {
         queue = append(queue, node.Right)
      }
      m[node.Val] = 1
   }
   return false
}

4、递归+二分查找；时间复杂度O(n)，空间复杂度O(n)

var arr []int

func findTarget(root *TreeNode, k int) bool {
   if root == nil {
      return false
   }
   arr = make([]int, 0)
   dfs(root)
   i := 0
   j := len(arr) - 1
   for i < j {
      if arr[i]+arr[j] == k {
         return true
      } else if arr[i]+arr[j] > k {
         j--
      } else {
         i++
      }
   }
   return false
}

func dfs(node *TreeNode) {
   if node == nil {
      return
   }
   dfs(node.Left)
   arr = append(arr, node.Val)
   dfs(node.Right)
}

总结

Easy题目，题目同leetcode 653.两数之和IV-输入BST