路径

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

你有两个选择： A）认为。 B）搜索。在前几个谷歌点击，你可以找到这个：http://login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

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

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

1. 在分而治之的方法，你可能会以维护双方的迄今最长的路径结束了，只保留更长的时间。
2. 引用的解决方案进行两次遍历，一次是确定直径，另一次是打印。这是一个很好的窍门，可以解决我们不知道我们是否处于方法1最深处的问题。
3. 不是深度优先搜索，而是先做宽度优先搜索。使用队列。对于存储父级的每个节点，逐级进行。当您达到最后一级时（没有孩子添加到队列中），您可以轻松打印整个路径，因为最后打印的节点在最长路径上，并且您有父链接。

Answer 2

将节点结构添加属性struct node * next。在return语句之前，添加一行这样的tree->next = (ldiameter > rdiameter ? tree->left : tree->right)以获得较长路径节点作为下一个节点。调用diameter(root)之后，您应该能够遍历根中的所有下一个节点以打印最大路径。

Answer 3

我认为以下方法可能有效......在O（N）时间内计算直径如下。

// this is a c++ code 
int findDiameter(node *root, int &max_length, node* &max_dia_node, int parent[], node* parent_of_root){ 
    if(!root) return 0; 
    parent[root->val] = parent_of_root->val; 
    int left = findDiameter(root->left, max_length); 
    int right = findDiameter(root->right, max_length); 
    if(left+right+1 > max_length){ 
     max_dia_node = root; 
     max_length = left+right+1; 
    } 
    return 1 + max(left,right); 
} 

所以在这个函数中发生了一些事情。第一个max_length是计算树的最大直径。并且，我将max_dia_node分配给此节点。

这是我将通过其最大直径的节点。

现在使用此信息，我们可以找到此节点的最大深度左侧子节点（max_dia_node）。从中我们可以通过“父”数组获得实际的节点。

这是树的两个遍历。