Description
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
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:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28 Output: false
Example 3:
Input: root = [2,1,3], k = 4 Output: true
Example 4:
Input: root = [2,1,3], k = 1 Output: false
Example 5:
Input: root = [2,1,3], k = 3 Output: true
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -104 <= Node.val <= 104rootis guaranteed to be a valid binary search tree.-105 <= k <= 105
Explanation
Inorder traverse the binaray search tree to build a list of node values in ascending order. Then use two pointers technique to find whether there are two elements adding up together equal to k.
Python Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
values = []
self.inorder_traverse(root, values)
left = 0
right = len(values) - 1
while left < right:
if values[left] + values[right] < k:
left += 1
elif values[left] + values[right] > k:
right -= 1
else:
return True
return False
def inorder_traverse(self, root, results):
if not root:
return
self.inorder_traverse(root.left, results)
results.append(root.val)
self.inorder_traverse(root.right, results)
- Time Complexity: O(N).
- Space Complexity: O(N).