英文:
Why can't I get the height of a BST in one statement (Java)
问题
我正在学习关于二叉搜索树，一个练习问题涉及递归地找到树的高度。
这是被接受的 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));
}
然而，当我尝试提交第二个语句时，它给了我一个运行时错误和 NPEs（NullPointerExceptions）。是 if (root == null){return -1}; 是第二个语句隐含的基本情况吗？
英文:
I was learning about binary search trees, and a practice problem involved recursively finding the height of the tree.
This is the Java code that was accepted:
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;
}
}
And this was the code (given as pseudocode in the tutorial) I tried at first and thought would work:
public static int getHeight(Node root){
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
However when I went to submit the second statement, it gave me a runtime error and NPEs. Is the if (root == null){return -1}; a base case that the second statement doesn't implicitly have?
答案1
得分: 1
是的，当root为空时，就会调用root.left，这就是为什么会得到空指针异常（NPE）。
而递归函数需要一个基本情况，不再调用递归函数。在这里，当root为空时，这意味着你在root.left或root.right上调用了getHeight()，其中root是树的叶子节点，这就是基本情况。
英文:
Yes, when root is null then root.left is called that's why you are getting NPE.
And recursive function needs a base case which not called the recursive function again. Here, when root is null that means you are calling getHeight() on root.left or root.right where root is leaves of the tree that is the base case.
答案2
得分: 0
@Eklavya在这里给出了正确的答案，但由于你正在学习，我喜欢递归，所以有几个好的经验法则要添加。
- 在你的代码中始终明确地设置终止条件。隐式地进行终止可能很聪明，但是沟通和维护起来很困难。
- 在Java中，除非你已经明确地注释了其他情况，否则请始终假设方法中的值为null。未受保护的子级访问始终是一种代码异味。
- 在大多数具有显式隐私（如Java）的语言中，最佳做法是不直接使用成员，而是构建一个接口，并从接口引用方法（使用
root.left()而不是root.left）。现在可能有点痛苦，但如果这是你保持的习惯，它将为你节省成千上万小时的浪费。
英文:
@Eklavya has the right answer here, but since you're learning and I love recursion a couple good rules of thumb to add.
- Always have a termination condition in your code explicitly. Making termination implicit may be clever but communicating it and maintaining it are hard
- In Java, always assume a value is null in your method unless you have specifically annotated it otherwise. Unprotected child access is always a code smell
- Best practice in most languages with explicit privacy (like Java) is not to use members directly but to build an interface and reference methods from the interface (
root.left()notroot.left). It's a bit of pain now, but it will save you thousands of wasted hours if it's a habit you stay in.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论