找到一個節點和樹的根之間的距離

我創建了一個方法來查找特定節點和樹的根之間的距離，我想驗證這是否是最簡單的方法這樣做。我有點擔心持有者會成爲最初的節點，因此，當我向上移動樹時，我正拉着我的節點。找到一個節點和樹的根之間的距離

public int distanceToRoot(Node node) 
{ 
    Node holder= node; 
    int distance=0; 
    if (node.getParent()==null) 
    { 
     distance=0; 
    } 
    else 
    { 
     while (holder.getParent() !=null) 
      { 
      holder=holder.getParent(); 
      distance++; 
      } 
    } 
    return distance; 
}

來源

2016-01-23 Maoster

的初始距離被稱爲整個'IF-THEN-else'結構是不必要的。只有循環會得到相同的結果。 –

甜，我只是擔心，使節點equivlant會鏈接內存地址類似於如果你用數組做，然後運行循環會毀了樹 – Maoster

下面是做這件事：

public int distanceToRoot(Node node) 
{ 
    if (node == null) 
     /* what do you want to do in this case */; 
    int d = 0; 
    for(Node p=node.getParent(); p!=null; p=p.getParent()) d++; 
    return d; 
}

來源

2016-01-23 01:25:45

它可以通過遞歸來完成。從任何子節點開始，向上遍歷父節點。找到它時，返回距離。

public int distanceToRoot(Node node, int distance){ 
    // If no parent it must be the root, return whatever value distance currently is 
    if (node.getParent()==null) return distance; 

    // Otherwise, recurse passing in this node's parent and current distance plus 1 
    return distanceToRoot(node.getParent(), distance + 1); 
}

應該具有零

int dist = distanceToRoot(aNode, 0);

來源

2016-01-23 01:31:03

記住，只是因爲遞歸是「酷」並不意味着它是最好的工具，即使它是天作之合。最好的例子就是計算斐波納契數。雖然_mathematical_函數是遞歸定義的，但對於較大的值，遞歸實現會由於每個值的雙重分支而吞噬大量堆棧空間 - 除非添加中間結果的記憶，此時您的數量級更復雜比簡單的循環。 –

是的。但由於它是尾遞歸的，因此不需要保存堆棧幀，因爲不需要通過它們返回。 –

尾遞歸斐波那契序列比正常遞歸版本更有效，因爲正常遞歸版本需要遞歸直到基本情況得到滿足，然後通過棧幀返回以乘以每個幀的「n」值（即第一個調用斐波那契函數是實際返回解的那個函數）。在尾遞歸函數中，當滿足基本情況時，答案是已知的，而不必返回任何先前的堆棧幀。 OP要求簡單，所以遞歸解決方案出現在我的腦海。我不知道遞歸被認爲是「很酷」 –

找到一個節點和樹的根之間的距離

回答

相關問題