LeetCode 653. Two Sum IV

题目描述

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

tag

k-sum题 二叉树 二叉搜索树

样例

1
2
3
4
5
6
7
8
9
10
输入: 
5
/
3 6
/
2 4 7

Target = 9

输出: True

算法

(哈希表) O(n)
思路
复杂度分析

最多树中每个节点遍历一遍。

python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class :
def findTarget(self, root: TreeNode, k: int) -> bool:
stack = [root]
table = set()
while stack:
node = stack.pop()
if node:
if k - node.val in table:
return True
else:
table.add(node.val)
stack.append(node.left)
stack.append(node.right)
return False

算法2

(双指针)
思路

类似在数组中的双指针操作,但是在本题BST中。l += 1的操作变成BST在中序遍历序列中的下一个更大元素,r -= 1的操作变成上一个更小元素。

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106071/Iterative-solution-with-O(n)-time-O(logn)-space-with-detailed-explanation.-Only-traverse-the-binary-tree-once!!!-time-O(logn)-space-with-detailed-explanation.-Only-traverse-the-binary-tree-once!!!)

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106086/Two-Pointer-on-BST-Solution-using-generator-in-python-(O(n)-time-O(logn)-space-if-BST-is-balanced)-time-O(logn)-space-if-BST-is-balanced))

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/299778/Python-Stack-based-two-pointer-DFS-solution-O(n)-time-O-(log-n)-space-for-balanced-trees-time-O-(log-n)-space-for-balanced-trees)

复杂度分析
python 代码