-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBST Maximum Difference
More file actions
25 lines (24 loc) · 844 Bytes
/
BST Maximum Difference
File metadata and controls
25 lines (24 loc) · 844 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public static int minpath(Node root){
if(root == null) return 0;
int sum = root.data;
if(root.left == null) sum += minpath(root.right);
else if(root.right == null) sum += minpath(root.left);
else sum += Math.min(minpath(root.left), minpath(root.right));
return sum;
}
public static int maxDifferenceBST(Node root,int target)
{
int rootsum = 0, leafsum = 0;
while(root!= null){
rootsum += root.data;
if(target==root.data) break;
if(target<root.data) root = root.left;
else root = root.right;
}
if(root == null) return -1;
leafsum = minpath(root);
return rootsum - leafsum;
}
}