c++ - 二叉树直径的路径

Question

我有一个二叉树和一个计算最长路径(直径)大小的方法:

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));
} 

我希望该函数还返回确切路径(直径所有节点的列表)。我该怎么做？

谢谢

Answer 1

您有两个选择:一)思考。B) 搜索。在前几个谷歌搜索中，你可以找到这个:http://login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

如果你想学习就选A)，如果你不关心就选B)，只想要一个快速但不一定完美的解决方案。

有很多可能的解决方案，其中一些:

1. 在分而治之的方法中，您可能最终会在两侧保持迄今为止最长的路径，并且只保留较长的路径。
2. 引用的解决方案执行两次遍历，一次用于确定直径，第二次用于打印。这是克服方法 1 中不知道我们是否处于最深点的问题的好技巧。
3. 不要进行深度优先搜索，而应进行广度优先搜索。使用队列。对于每个存储父节点的节点，逐级进行。当您到达最后一层(没有 child 添加到队列中)时，您可以轻松打印整个路径，因为最后打印的节点位于(一个)最长路径上，并且您有父链接。