为什么我不能在一个语句中得到BST的高度(Java)

Question

我学习了二进制搜索树，还有一个练习问题涉及递归查找树的高度。

这是被接受的Java代码：

public static int getHeight(Node root){
if (root == null)
return -1;
else {
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
}   

这就是我最初尝试的代码(在教程中以伪代码的形式给出(，我认为它会起作用：

public static int getHeight(Node root){
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}   

然而，当我提交第二条语句时，它给了我一个运行时错误和NPE。if (root == null){return -1};是第二个语句没有隐含的基本情况吗？

Answer 1

是的，当root为null时，会调用root.left，这就是为什么要获得NPE。

并且递归函数需要一个基本情况，该基本情况不再调用递归函数。这里，当root是null时，意味着您在root.left或root.right上调用getHeight()，其中root是作为基本情况的树的叶子。

Answer 2

@Eklavya在这里有正确的答案，但由于您正在学习，而且我喜欢递归，因此需要添加一些好的经验法则。

• 在代码中总是显式地有一个终止条件。隐含终止可能很聪明，但沟通和维护它很难
• 在Java中，总是假设方法中的值为null，除非您对其进行了特殊注释。未受保护的子访问始终是一种代码气味
• 大多数具有显式隐私的语言(如Java(的最佳实践不是直接使用成员，而是从接口构建接口和引用方法(root.left()而不是root.left(。现在这有点痛苦，但如果你养成习惯，它会为你节省数千个浪费的小时