当前位置: 动力学知识库 > 问答 > 编程问答 >

java - Print the diameter of the BST

问题描述:

I have written a program to find the diameter of the BST... Can some one give me some ideas on how I can print the nodes (root.data) of the max Diameter I found?

private int maxDia(Node root) {

if(root==null) {

return 0;

}

else{

int llen = maxDepth(root.left);

int rlen = maxDepth(root.right);

int ldia = maxDia(root.left);

int rdia = maxDia(root.right);

return Math.max(llen+rlen+1,Math.max(ldia,rdia));

}

}

PS : Max depth finds out the height of the tree.

Thanks

网友答案:

Pseudocode:

printDia(root):
    if diameter goes through root:
        printFromDeepest(root.left)
        print(root)
        printToDeepest(root.right)
    else if diameter is in root.left:
        printDia(root.left)
    else:
        printDia(root.right)
网友答案:
 struct node
{    
node* left,right;
int data; 
};
struct path
{
 node *nodepointer;
 int length;
 };
int flag=0;

 node *x,*y,*lca;

 path *printpath(node *leaf,int d)
{
if(flag==0)
{
path *dia= new path;
dia->length=0;
dia->nodepointer=NULL;

if(leaf==NULL)
return dia;

path *a=new path;
path *b=new path;
a=printpath(leaf->left,d);
b=printpath(leaf->right,d);


if(a->length + b->length + 1 == d )
{
    lca=leaf;
    x=a->nodepointer;
    y=b->nodepointer;
    flag=1;
}

dia->length=max(a->length,b->length)+1;

if(a->length > b->length && a->nodepointer!=NULL)
{
    dia->nodepointer=a->nodepointer;
}
if(b->length >= a->length && b->nodepointer!=NULL)
{
    dia->nodepointer=b->nodepointer;
}
if(a->nodepointer==NULL && b->nodepointer==NULL)
{
        dia->nodepointer=leaf;
}

return dia;

}

}
分享给朋友:
您可能感兴趣的文章:
随机阅读: