网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 650. 只有两个键的键盘 ，难度为 简单。
Tag : 「二叉树」、「迭代」、「中序遍历」、「双指针」、「哈希表」、「树的搜索」
给定一个二叉搜索树 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, 10^4][1,104]
- -10^4 <= Node.val <= 10^4−104<=Node.val<=104
root为二叉搜索树- -10^5 <= k <= 10^5−105<=k<=105
哈希表 + 树的搜索
在递归搜索过程中记录下相应的节点值（使用 Set 集合），如果在遍历某个节点 xx 时发现集合中存在 k - x.valk−x.val，说明存在两个节点之和等于 kk，返回 True，若搜索完整棵树都没有则返回 False。
代码：
class Solution { Set<Integer> set = new HashSet<>(); public boolean findTarget(TreeNode root, int k) { if (root == null) return false; if (set.contains(k - root.val)) return true; set.add(root.val); return findTarget(root.left, k) | findTarget(root.right, k); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
双指针 + BST 中序遍历
解法一中没有利用 BST 特性，利用 BST 中序遍历有序的特性，我们可以实现类似「双指针」的效果。
起始先让 BST 的最左链和最右链完全入栈，此时栈顶元素为 BST 中的最小值和最大值，分别使用 l 和 r 充当指针代指，根据两指针指向的节点值之和与 kk 的大小关系来指导如何让 l 和 r 移动，l 的移动过程其实就是找下一个比 l.val 更大的值，而 r 的移动过程其实就是找下一个比 r.val 更小的值。
代码：
class Solution { public boolean findTarget(TreeNode root, int k) { Deque<TreeNode> ld = new ArrayDeque<>(), rd = new ArrayDeque<>(); TreeNode temp = root; while (temp != null) { ld.addLast(temp); temp = temp.left; } temp = root; while (temp != null) { rd.addLast(temp); temp = temp.right; } TreeNode l = ld.peekLast(), r = rd.peekLast(); while (l.val < r.val) { int t = l.val + r.val; if (t == k) return true; else if (t < k) l = getNext(ld, true); else r = getNext(rd, false); } return false; } TreeNode getNext(Deque<TreeNode> d, boolean isLeft) { TreeNode cur = d.pollLast(); TreeNode node = isLeft ? cur.right : cur.left; while (node != null) { d.addLast(node); node = isLeft ? node.left : node.right; } return d.peekLast(); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.653 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
