653. Two Sum IV - Input is a BST

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Constraints:

• The number of nodes in the tree is in the range $[1, 10^4]$.
• $-10^4 <= Node.val <= 10^4$
• root is guaranteed to be a valid binary search tree.
• $-10^5 <= k <= 10^5$

Code

class Solution {
    TreeNode root;
    public boolean findTarget(TreeNode root, int k) {
        if(this.root == null) this.root = root;
        if (root == null) return false;

        if (search(root, k - root.val)) return true;
        return findTarget(root.left, k) || findTarget(root.right, k);
    }

    public boolean search(TreeNode node, int k) {
        TreeNode curr = this.root;

        while (curr != null) {
            if (k > curr.val) {
                curr = curr.right;
            } else if (k < curr.val) {
                curr = curr.left;
            } else {
                return curr != node ? true : false;
            }
        }

        return false;
    }
}

• Time Complexity: O(nh)
• Space Complexity: O(h)
• h is the height of the tree, which is logn at best case, n at worst case.

     3
    /
   2
  /
 1

Searching in BST: For searching element 1, we have to traverse all elements (in order 3, 2, 1). Therefore, searching in binary search tree has worst case complexity of O(n). In general, time complexity is O(h) where h is height of BST.

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return helper(root, k, new HashSet<>());
    }

    private boolean helper(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;

        set.add(root.val);

        return helper(root.left, k, set) || helper(root.right, k, set);
    }
}