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函数来确定最接近根的叶节点。请注意，这个想法适用于计算距离，而不是实际（最近的）叶节点本身。我认为实施这个应该不会太困难。如果您有任何其他问题，请随时询问。