動機

主要是紀錄在tree上做這題的做法

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 = 9Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28Output: false

Example 3:

Input: root = [2,1,3], k = 4Output: true

Example 4:

Input: root = [2,1,3], k = 1Output: false

Example 5:

Input: root = [2,1,3], k = 3Output: true

 

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

Sol: preorder + 2sum

先走preorder，就會有sorted list，接下去就是2sum

class Solution:
	def preorder(self, r):
		if not r:
			return
		else:
			self.preorder(r.left)
			self.ret.append(r.val)
			
			self.preorder(r.right)

	def findTarget(self, root: TreeNode, k: int) -> bool:
		self.ret = []
		self.preorder(root)
		print(self.ret)
		i, j = 0, len(self.ret) - 1
		while i < j:
			if self.ret[i] + self.ret[j] == k:
				return True
			elif self.ret[i] + self.ret[j] < k:
				i += 1
			else:
				j -= 1
		return False

case study: recur + hash

用hash記錄看過的數字，等到遇到對的數字

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);
    }
}