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

中序遍历+哈希

  1. class Solution {
  2.     public boolean findTarget(TreeNode root, int k) {
  3.         Set<Integer> set = new HashSet<>();
  4.         Deque<TreeNode> stack = new ArrayDeque<>();
  5.         while (root != null || !stack.isEmpty()) {
  6.             if (root != null) {
  7.                 stack.push(root);
  8.                 root = root.left;
  9.             } else {
  10.                 TreeNode node = stack.poll();
  11.                 if (set.contains(k - node.val)) return true;
  12.                 set.add(node.val);
  13.                 root = node.right;
  14.             }
  15.         }
  16.         return false;
  17.     }
  18. }

dfs+哈希

  1. class Solution {
  2.     Set<Integer> set = new HashSet<>();
  3.     public boolean findTarget(TreeNode root, int k) {
  4.         if (root == null) return false;
  5.         if (set.contains(k-root.val)) return true;
  6.         set.add(root.val);
  7.         boolean left = findTarget(root.left,k);
  8.         boolean right = findTarget(root.right,k);
  9.         return left || right;
  10.     }
  11. }

中序遍历 + 双指针

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     //利用bst中序遍历有序特性，利用双指针来实现，可以用左右两个栈来实现左右两个指针
  18.     public boolean findTarget(TreeNode root, int k) {
  19.         TreeNode tem = root;
  20.         Deque<TreeNode> ls = new LinkedList<>(), rs = new LinkedList<>();
  21.         while (tem != null) {
  22.             ls.addLast(tem);
  23.             tem = tem.left;
  24.         }
  25.         tem = root;
  26.         while (tem != null) {
  27.             rs.addLast(tem);
  28.             tem = tem.right;
  29.         }
  30.         //此时左右两个栈分别存放的是最小值和最大值
  31.         TreeNode l = ls.peekLast(), r = rs.peekLast();
  32.         while (l.val < r.val) {
  33.             int t = l.val + r.val;
  34.             if (t == k) return true;
  35.             if (t < k) l = getNext(ls, true);
  36.             else r = getNext(rs, false);
  37.         }
  38.         return false;
  39.     }
  41.     TreeNode getNext(Deque<TreeNode> stk, boolean flag) {
  42.         TreeNode node = flag ? stk.pollLast().right : stk.pollLast().left;
  43.         while (node != null) {
  44.             stk.addLast(node);
  45.             //左子树就要找下一个大的，右子树找上一个大的
  46.             node = flag ? node.left : node.right;
  47.         }
  48.         return stk.peekLast();
  49.     }
  50. }