Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
Approach:
1. Store all the paths from root to leafs.
2. for each path i,j from root to leaf calculate
a = sum of nodes in the path from root to X
b = sum of nodes in the path from root to Y
c = sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
Let max fxy be the maximum for F(X,Y).
if ((a+b-c) > fxy) { fxy <= (a+b-c) } and also store the leaf(i) and leaf(j).
Code input/output:
printing inorder:
1 3 4 6 7 8 10 13 14
printing the path map:
{0=[8, 3, 1], 1=[8, 3, 6, 4], 2=[8, 3, 6, 7], 3=[8, 10, 14, 13]}
12:21:11
1 : 4
12:24:11
1 : 7
12:45:8
1 : 13
21:24:17
4 : 7
21:45:8
4 : 13
24:45:8
7 : 13
Max F(X,Y): 61
Leaf1: 7
Leaf2: 13
No comments:
Post a Comment