Created
March 21, 2018 06:18
-
-
Save jianminchen/cabf4820725eb5a148bc1320b31ea39d to your computer and use it in GitHub Desktop.
Find second largest element in the binary search tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
10:32 pm | |
Find second largest element in binary search tree | |
stack iterative traversal of first 2 elements | |
time o(n) space o(n) | |
if tree has less than 2 elements return null | |
Ex 1 res=5 | |
10* no right child, so no larger element, 10 is largest possible element | |
5* 5,10 | |
10* no right child, so no larger element, 10 is largest possible element | |
5* 5,10 since 5 has right child, right child must be larger | |
1 8* 8,10 ret 8 | |
10* no right child, so no larger element, 10 is largest possible element | |
5* 5,10 since 5 has right child, right child must be larger | |
1 8* 8,10 child is left which is smaller, does not affect result | |
6 | |
10* no right child, so no larger element, 10 is largest possible element | |
5* 5,10 since 5 has right child, right child must be larger | |
1 8* 8 has right child, has to be larger | |
6 9 9,10 | |
result=9 | |
10//10 | |
9//9,10 | |
8//left is smaller, queue is full, so doesn't matter | |
7 | |
ascending pq | |
3 | |
2 | |
1 | |
4 | |
2 | |
1 3 | |
[4, 2, 3] | |
10 | |
5 15* | |
8 13* | |
14* | |
3* | |
2* | |
1* | |
*/ | |
10X,13X,14,15 | |
public int secondLargestBSTNode(TreeNode root){ | |
//null check, return -1 | |
int result = -1; | |
PriorityQueue<Integer>pq=new PriorityQueue<>(); | |
while(root != null){//2 | |
pq.offer(root.val);//1,2,3 | |
if(pq.size()>2){ | |
pq.poll();//2,3 | |
} | |
if(root.right != null){ | |
root = root.right;// | |
} | |
else{ | |
root = root.left;//null | |
} | |
} | |
//need check pq.size()==2 | |
return pq.poll();//14 | |
} | |
time | |
tree ologn | |
k=2 | |
o*k (log n) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment