Java的二叉搜索樹_從根到最近的葉子

Question

我想知道基本的算法來計算二叉搜索樹

我想用這樣的代碼從根 最接近葉距離的距離，

public int closeness() { 
    return closeness(root); 
} 

public int closeness(Node x) { 

} 

謝謝。

Answer 1

你需要採取的最低的每一個分支的「接近性」加一：

public int closeness(Node x) { 
    if (x == null) { 
    return Integer.MAX_VALUE; 
    } 
    if (x.left == null && x.right == null) { 
    return 0; 
    } 
    return Math.min(closeness(x.left), closeness(x.right)) + 1; 
} 

或者稍微詳細無「MAX_VALUE」招忽略空分支Math.min（）

public int closeness(Node x) { 
    if (x.left == null) { 
    if (x.right == null) { 
     return 0; 
    } 
    return closedness(x.right) + 1; 
    } 
    if (x.right == null) { 
    return closedness(x.left) + 1; 
    } 
    return Math.min(closeness(x.left), closeness(x.right)) + 1; 
} 

Answer 2

實現您的需求的一個快速構思是遞歸地遍歷BST（左和右子樹）並沿途計算在到達葉節點之前必須經過的節點數。最後，您可以使用簡單的MIN/MAX函數來確定最接近根的葉節點。請注意，這個想法適用於計算距離，而不是實際（最近的）葉節點本身。我認爲實施這個應該不會太困難。如果您有任何其他問題，請隨時詢問。