路徑

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）。從中我們可以通過「父」數組獲得實際的節點。

這是樹的兩個遍歷。