二進制搜索樹遞歸地返回到根

-4

我需要在java中創建一個方法，遞歸確定從任何給定節點返回到根的距離。該方法返回一個整數，顯示特定節點離開根節點的距離。節點類別如下二進制搜索樹遞歸地返回到根

Public class Node 
{ 
int data; 
node left; 
node right; 
}

沒有全局變量或屬性允許，我不能修改節點類。我查過它，每個解決方案都告訴我修改節點類以包含父節點的節點指針。任何幫助將不勝感激，謝謝！

來源

2015-04-27 SScoder93

你的問題是什麼？ –

請不要要求我們爲你做功課。 –

只需從根計數步數中找到此節點的路徑即可。 –

如果您有parent存儲在每個節點中，搜索將需要O（log N）操作（如果是平衡樹） - 您只需通過父母並計算步驟，直到parent == null這意味着根節點。

但是如果沒有parent字段，則需要遞歸遍歷從根開始的整個樹，查找給定節點。它需要O（N）操作：

/** Returns the distance between "n" and "current" plus "step" 
/* or -1 if "n" not found          */ 
int distance(Node n, Node current, int step) { 
    int res = -1; 
    if (n == current) // node found 
     return step;      
    if (current.left == null && current.right == null) // leaf node 
     return -1; 
    if (current.left != null) // search in left subtree 
     res = distance(n, current.left, step + 1); 
    if (res > 0) 
     return res; 
    if (current.right != null) // search in right subtree 
     res = distance(n, current.right, step + 1); 
    return res; 
} 

//.... 
Node root; 
Node given; 
int dist = distance(given, root, 0); // distance between "root" and "given"

來源

2015-04-27 14:40:15

二進制搜索樹遞歸地返回到根

回答

相關問題