Java二叉搜索树_根到最近叶子的距离

Question

我想知道计算离根最近的叶子距离的基本算法在二叉搜索树中

我想使用这样的代码，

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

public int closeness(Node x) {

}

谢谢。

Answer 1

实现您的要求的一个快速想法是递归遍历您的 BST（左子树和右子树）并沿途计算在到达叶节点之前必须经过的节点数。最后，您可以使用一个简单的 MIN/MAX 函数来确定距离根最近的叶节点。请注意，这个想法适用于计算距离而不是实际（最近的）叶节点本身。我认为实施起来应该不会太困难。如果您有任何其他问题，请随时提出。

Answer 2

您需要取每个分支的 "closeness" 中的最小值加一：

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;
}

Java二叉搜索树_根到最近叶子的距离

Java Binary Search Tree _ the distance from root to nearest leaf

java

binary-search-tree