二叉树的直径的路径(Path of the diameter of a binary tree)

二叉树的直径的路径(Path of the diameter of a binary tree)

我有一个二叉树和一个最长路径（直径）的大小的方法：

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

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

谢谢

I have a binary tree and a method for the size of the longest path (the diameter):

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

I want the function to return also the exact path (list of all the nodes of the diameter). How can I do it?

Thanks

最满意答案

您有两种选择：A）思考。 B）搜索。 在最初的几个谷歌点击中你可以找到这个： http ： //login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

选择A）如果你想学习，选择B）如果你不在乎，只需要一个快速的，尽管不一定完美的解决方案。

有许多可能的解决方案，其中一些：

在分而治之的方法中，你可能最终会保持两边最长的路径，并且只保留更长的路径。 引用的解决方案进行两次遍历，一次用于确定直径，第二次用于打印。 这是一个很好的技巧来克服不知道我们是否处于方法1中最深处的问题。 而不是深度优先搜索，先做一个广度。 使用队列。 对于存储父级的每个节点，逐级进行。 当您到达最后一级（没有子项添加到队列中）时，您可以轻松打印整个路径，因为最后一个打印节点位于（一个）最长路径上，并且您具有父链接。

You have two options: A) Think. B) Search. Among the first few google hits you can find this: http://login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

Choose A) if you want to learn, choose B) if you do not care, only want a quick, albeit not necessarily perfect solution.

There are many possible solutions, some of them:

In a divide and conquer approach you will probably end up with maintaining the so far longest paths on both sides, and keep only the longer. The quoted solution does two traversals, one for determining the diameter, and the second for printing. This is a nice trick to overcome the problem of not knowing whether we are at the deepest point in approach 1. Instead of a depth first search, do a breadth first one. Use a queue. Proceed level by level, for each node storing the parent. When you reach the last level (no children added to queue), you can print the whole path easily, because the last printed node is on (one) longest path, and you have the parent links.