Given a BST:
10
7 14
4 8 12 19
13 16 20
[4,7,8,10,12,13,14,16,19,20]
Q1. Find smallest larger element than target,
Example: input: target = 13, output: 14
Q2. Find largest smaller element than target,
Example: input: target = 13, output: 12
Answer:
public class Solution {
//Q1. Find smallest larger element than target: Time:O(logn), Space:O(1)
public static int findNLR(TreeNode root, int target, int min, int max) throws Exception{
//if root.val > target, return the smallest element in the subtree
if(root.val > target){
if(root.left != null){
//go left branch
return findNLR(root.left, target, min, root.val);
}else{
return root.val;
}
}
else{
if(root.right != null){
//go right branch
return findNLR(root.right, target, root.val, max);
}else{
if(max != Integer.MAX_VALUE){
return max;
}
else{
throw new Exception();
}
}
}
}
public static int findNL(TreeNode root, int target) throws Exception{
return findNLR(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
//Q2. Find largest smaller element than target: Time:O(logn), Space:O(1)
public static int findPSL(TreeNode root, int target, int min, int max) throws Exception{
//if root.val < target, return the largest element in the subtree
if(root.val < target){
if(root.right!=null){
//go right branch
return findPSL(root.right, target, root.val, max);
}else{
return root.val;
}
}
else{
if(root.left!=null){
//go left branch
return findPSL(root.left, target, min, root.val);
}else{
if(min != Integer.MIN_VALUE){
return min;
}
else{
throw new Exception();
}
}
}
}
public static int findPS(TreeNode root, int target) throws Exception{
return findPSL(root, target, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public static void main(String[] args) throws Exception {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(7);
root.right = new TreeNode(14);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(8);
root.right.left = new TreeNode(12);
root.right.left.right = new TreeNode(13);
root.right.right = new TreeNode(19);
root.right.right.left = new TreeNode(16);
root.right.right.right = new TreeNode(20);
int res = findNL(root, 13);
System.out.println(res);
}
}
No comments:
Post a Comment