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

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”技巧来忽略数学中的空分支，则会更加冗长。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函数来确定距离根最近的叶节点。请注意，该想法用于计算距离，而不是实际（最近的）叶节点本身。我认为，实现这一点应该不会太困难。如果您还有任何问题，请随时提问