c++ - 打印 BST 的 Diameter 对应的节点组成的路径

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. 遍历子树时，增加深度。
6. 如果depth大于max_height，设置max_height为深度。
7. 从子树返回时，递减depth。

这里假设读者知道如何遍历二叉树；这是另一篇文章的主题。