Question

Formatted question description: https://leetcode.ca/all/653.html

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

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⁴].
-10⁴ <= Node.val <= 10⁴
root is guaranteed to be a valid binary search tree.
-10⁵ <= k <= 10⁵

Algorithm

As long as it is the question of the sum of two numbers, you must remember to try to do it with HashSet.

This question is just to turn the array into a binary tree. We need to traverse the binary tree and use a HashSet. In the recursive function function,

if node is empty, return false.
If k minus the current node value exists in the HashSet, return true directly;
otherwise, add the current node value to the HashSet, and then call the recursive function on the left and right sub-nodes and return together.

Code

public class Two_Sum_IV_Input_is_a_BST {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    // https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
    public class Solution_queue {
        public boolean findTarget(TreeNode root, int k) {
            Set<Integer> set = new HashSet<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                if (queue.peek() != null) {
                    TreeNode node = queue.remove();
                    if (set.contains(k - node.val))
                        return true;
                    set.add(node.val);
                    queue.add(node.right);
                    queue.add(node.left);
                } else
                    queue.remove();
            }
            return false;
        }
    }

    // time: O(N)
    // space: O(N)
    public class Solution_usingBST { // inorder traversal to get sorted list
        public boolean findTarget(TreeNode root, int k) {
            List< Integer > list = new ArrayList<>();
            inorder(root, list);
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int sum = list.get(l) + list.get(r);
                if (sum == k)
                    return true;
                if (sum < k)
                    l++;
                else
                    r--;
            }
            return false;
        }
        public void inorder(TreeNode root, List < Integer > list) {
            if (root == null)
                return;
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

    // time: O(N)
    // space: O(N)
    public class Solution {
        public boolean findTarget(TreeNode root, int k) {
            Set < Integer > set = new HashSet();
            return find(root, k, set);
        }

        public boolean find(TreeNode root, int k, Set< Integer > set) {
            if (root == null) {
                return false;
            }
            if (set.contains(k - root.val)) {
                return true;
            }
            set.add(root.val);

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

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Set<Integer> set = new HashSet<Integer>();

    public boolean findTarget(TreeNode root, int k) {
        prePost(root);
        for (int key : set) {
            if (set.contains(k - key) && k - key != key)
                return true;
        }
        return false;
    }

    public void prePost(TreeNode root) {
        if (root == null)
            return;
        set.add(root.val);
        prePost(root.left);
        prePost(root.right);
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Set<Integer> vis = new HashSet<>();
    private int k;

    public boolean findTarget(TreeNode root, int k) {
        this.k = k;
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return false;
        }
        if (vis.contains(k - root.val)) {
            return true;
        }
        vis.add(root.val);
        return dfs(root.left) || dfs(root.right);
    }
}

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
// Time: O(NH)
// Space: O(H)
class Solution {
    bool dfs(TreeNode *root, int k, int mn = INT_MIN, int mx = INT_MAX) {
        if (!root || root->val <= mn || root->val >= mx) return false;
        if (root->val == k) return true;
        return root->val < k ? dfs(root->right, k, root->val, mx) : dfs(root->left, k, mn, root->val);
    }
    bool find(TreeNode *root, int k, TreeNode *from) {
        if (!root) return false;
        if (2 * root->val != k && dfs(from, k - root->val)) return true;
        return find(root->left, k, from) || find(root->right, k, from);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        return find(root, k, root);
    }
};

class BSTIterator:
    def __init__(self, root: Optional[TreeNode], leftToRight: bool):
        self.stack = []
        self.leftToRight = leftToRight
        self._pushUntilNone(root)

    def next(self) -> int:
        node = self.stack.pop()
        if self.leftToRight:
            self._pushUntilNone(node.right)
        else:
            self._pushUntilNone(node.left)
        return node.val

    # if passed in a None node, then None will not be pushed to stack
    def _pushUntilNone(self, root: Optional[TreeNode]):
        while root:
            self.stack.append(root)
            root = root.left if self.leftToRight else root.right


class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if not root:
            return False

        left = BSTIterator(root, True)
        right = BSTIterator(root, False)

        l = left.next()
        r = right.next()
        while l < r:
            summ = l + r
            if summ == k:
                return True
            if summ < k:
                l = left.next()
            else:
                r = right.next()

        return False

###########

# 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: Optional[TreeNode], k: int) -> bool:
        def dfs(root):
            if root is None:
                return False
            if k - root.val in vis:
                return True
            vis.add(root.val)
            return dfs(root.left) or dfs(root.right)

        vis = set()
        return dfs(root)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if not root: return False
        bfs, s = [root], set()
        for i in bfs:
            print i.val
            if k - i.val in s : return True
            s.add(i.val)
            if i.left : bfs.append(i.left)
            if i.right : bfs.append(i.right)
            print([b.val for b in bfs])
        return False

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findTarget(root *TreeNode, k int) bool {
	vis := map[int]bool{}
	var dfs func(*TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return false
		}
		if vis[k-root.Val] {
			return true
		}
		vis[root.Val] = true
		return dfs(root.Left) || dfs(root.Right)
	}
	return dfs(root)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function findTarget(root: TreeNode | null, k: number): boolean {
    const dfs = (root: TreeNode | null) => {
        if (!root) {
            return false;
        }
        if (vis.has(k - root.val)) {
            return true;
        }
        vis.add(root.val);
        return dfs(root.left) || dfs(root.right);
    };
    const vis = new Set<number>();
    return dfs(root);
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::collections::{HashSet, VecDeque};
use std::rc::Rc;
impl Solution {
    pub fn find_target(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> bool {
        let mut set = HashSet::new();
        let mut q = VecDeque::new();
        q.push_back(root);
        while let Some(node) = q.pop_front() {
            if let Some(node) = node {
                let mut node = node.as_ref().borrow_mut();
                if set.contains(&node.val) {
                    return true;
                }
                set.insert(k - node.val);
                q.push_back(node.left.take());
                q.push_back(node.right.take());
            }
        }
        false
    }
}

653 - Two Sum IV - Input is a BST

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions