Вывести путь, состоящий из узлов, соответствующих диаметру BST
Я знаю, как найти диаметр 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
Решение
Вот алгоритм нахождения максимума глубина двоичного дерева:
- Пусть будет переменная под названием
max_height, - Инициализировать на ноль.
- Пусть будет переменная с именем
depth, - инициализировать
depthв ноль. - При переходе к поддереву увеличивается
depth, - Если
depthбольше, чемmax_height, задаватьmax_heightв
depth, - При возврате из поддерева, уменьшение
depth,
Это предполагает, что читатель знает, как пройти через двоичное дерево; это тема для другого поста.
Другие решения
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;
}
}
detector