Sponsored
Sponsored
This approach leverages the properties of a Binary Search Tree (BST). By performing an inorder traversal on a BST, we can obtain a sorted list of its elements. Once we have this sorted list, the problem reduces to finding two distinct numbers in this sorted array that sum up to the given target, k. This can efficiently be solved using the two-pointer technique.
Time Complexity: Perform O(n) for traversal and O(n) for two-pointer scan, hence O(n).
Space Complexity: O(n) to store the elements of the tree.
1import java.util.ArrayList;
2
3public class Solution {
4 public boolean findTarget(TreeNode root, int k) {
5 ArrayList<Integer> nums = new ArrayList<>();
6 inorder(root, nums);
7 int left = 0, right = nums.size() - 1;
8 while (left < right) {
9 int sum = nums.get(left) + nums.get(right);
10 if (sum == k) {
11 return true;
12 } else if (sum < k) {
13 left++;
14 } else {
15 right--;
16 }
17 }
18 return false;
19 }
20
21 private void inorder(TreeNode node, ArrayList<Integer> nums) {
22 if (node == null) return;
23 inorder(node.left, nums);
24 nums.add(node.val);
25 inorder(node.right, nums);
26 }
27
28 class TreeNode {
29 int val;
30 TreeNode left;
31 TreeNode right;
32 TreeNode(int x) { val = x; }
33 }
34}
35This Java solution uses an ArrayList to store sorted nodes. With two pointers, the sum check for k is performed efficiently.
This approach utilizes a hash set to store visited node values. We traverse the BST and for each node, check if k - node.val exists in the hash set. If it does, then a pair adding to k has been found.
Time Complexity: O(n), with a pass through each node.
Space Complexity: O(n) for storing nodes in the hash table.
1using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool FindTarget(TreeNode root, int k) {
HashSet<int> set = new HashSet<int>();
return Find(root, k, set);
}
private bool Find(TreeNode node, int k, HashSet<int> set) {
if (node == null) return false;
if (set.Contains(k - node.val)) return true;
set.Add(node.val);
return Find(node.left, k, set) || Find(node.right, k, set);
}
}
The C# solution employs a HashSet for its complement query ability, detecting when k can be achieved with visited nodes.