Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
void findlongest(struct tnode *root,int a[],int ind,int level,int *max,int path[])
{
if(root==NULL)
{
if(level>*max)
{
int i=0;
for(i=0;i<ind;i++)
path[i]=a[i];
*max=level;
}
return;
}
a[ind]=root->val;
findlongest(root->left,a,ind+1,level+1,max,path);
findlongest(root->right,a,ind+1,level+1,max,path);
}
int main()
{
int i,num;
struct tnode *root=NULL;
for(i=0;i<N;i++)
{
scanf("%d",&num);
root=addnode(root,num);
}
int a[100],leftpath[100],rightpath[100];
num=0;
findlongest(root->left,a,0,0,&num,leftpath);
while(num>0)
printf("%d\t",leftpath[--num]);
printf("%d\t",root->val);
num=0;
findlongest(root->right,a,0,0,&num,rightpath);
for(i=0;i<num;i++)
printf("%d\t",rightpath[i]);
printf("\n");
getch();
return 0;
}
Java solution. O(n)
public void printDiameter(Node root) {
List<String> maxDiameter = new ArrayList<String>();
if (null != root) {
root.getMaxRadius(maxDiameter);
}
for (String id : maxDiameter) {
// print id
}
}
public class Node() {
String id;
Node left;
Node right;
// return max radius (height or depth) of this subtree
// conditionally record diameter of this subtree
public List<String> getMaxRadius(List<String> maxDiameter) {
// fetch child radii
List<String> leftMaxRadius = null != left ? left.getMaxRadius(maxDiameter) : new ArrayList<String>();
List<String> rightMaxRadius = null != right ? right.getMaxRadius(maxDiameter) : new ArrayList<String>();
// test/set max diameter
if (leftMaxRadius.size() + rightMaxRadius.size() + 1 > maxDiameter.size()) {
maxDiameter.clear();
maxDiameter.addAll(leftMaxRadius);
maxDiameter.add(id);
maxDiameter.addAll(rightMaxRadius);
}
// return max radius
if (leftMaxRadius.size() > rightMaxRadius.size()) {
leftMaxRadius.add(id);
return leftMaxRadius;
}
else {
rightMaxRadius.add(0, id); // add to front to preserve order
return rightMaxRadius;
}
}
}
public int getMaxHeight(TreeJ root){
if (root==null) {
return 0;
}
return (Math.max(getMaxHeight(root.left),getMaxHeight(root.right))+1);
}
int diameter(TreeJ tree)
{
if (tree==null){
return 0;
}
int lheight = getMaxHeight(tree.left);
int rheight = getMaxHeight(tree.right);
int ldiameter = diameter(tree.left);
int rdiameter = diameter(tree.right);
return Math.max(lheight + rheight + 1, Math.max(ldiameter, rdiameter));
}
A tree's diameter must be like this: it has a node P as the center, with left radius being the longest path of P's left subtree and right radius being the longest path of P's right subtree.
So we divide the problem into two parts:
(1)traverse the whole tree and get the height of each subtree, meanwhile determine the diameter's center node P
(2)get the two radii of this diameter
Following is code in C++:
- uuuouou April 02, 2014