c++ - 打印与 BST 的直径对应的节点所包含的路径

Question

我知道如何找到 BST 的直径。

int diameter(struct node * tree)
{

if (tree == 0)
 return 0;


int lheight = height(tree->left);
int rheight = height(tree->right);

int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}




int height(struct node* node)
{

if(node == NULL)
   return 0;


return 1 + max(height(node->left), height(node->right));
}

我应该在代码中进行哪些更改以打印路径，即从一个叶节点到直径的另一个叶节点的顺序中与树的直径相对应的节点。

例如：-

                     8
                   /  \
                  1    12
                  \     /
                   5   9
                 /   \
                4     7
                     /
                    6

输出应该是 6 7 5 1 8 12 9

Answer 1

这是一个找到二叉树最大深度的算法：

1. 假设有一个名为 的变量max_height。
2. 初始化为零。
3. 假设有一个名为 的变量depth。
4. 初始化depth为零。
5. 遍历子树时，递增depth.
6. 如果depth大于max_height，设置max_height为 depth。
7. 从子树返回时，递减depth.

这假设读者知道如何遍历二叉树；这是另一个帖子的主题。

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;

}

}