打印BST的直徑

Question

我已經編寫了一個程序來查找BST的直徑......有人可以給我一些關於如何打印我找到的最大直徑的節點（root.data）的想法嗎？

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：最大深度找出樹的高度。

感謝

Answer 1

僞代碼：

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) 

Answer 2

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; 

} 

}