653. Two Sum IV - Input is a BST (M)
Last updated
Last updated
Given the root
of a Binary Search Tree and a target number k
, return true
if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Example 2:
Constraints:
The number of nodes in the tree is in the range [1, 104]
.
-104 <= Node.val <= 104
root
is guaranteed to be a valid binary search tree.
-105 <= k <= 105
Solution 1: hashset + DFS, Time Complexity:O(n)
, Space Complexity:O(n)
Solution 2: inorder traversal得到递增的array,two pointers. Time Complexity:O(n)
, Space Complexity:O(n)