计算树中从根到最远节点的边的方法

Question

我正在尝试编写一种方法来计算从根节点到最远节点所采用的最大边数。

public static int depth(Tree t) {
    if(t == null) return 0;
    else return 1 + Math.max(depth(t.left), depth(t.right));
}

对于这棵树，该方法应该显示答案 3，但是它目前给出的结果是 4，因为它计算的是节点而不是边，因此计算的是初始根。我将如何改变它以给出正确的结果？

Answer 1

将您的递归方法包装在外部方法中，该方法测试 null 树并从结果中减去一个：

public static int depth(Tree t) {
  return (t == null) ? 0 : calculateDepth(t) - 1;
}

private static int calculateDepth(Tree t) {
  if (t == null)
    return 0;
  else
    return 1 + Math.max(calculateDepth(t.left), calculateDepth(t.right));
}

计算树中从根到最远节点的边的方法

Method to count edges from root to furthest node in tree

java

recursion

tree

edges