查找二叉树的高度

Question

我写了以下代码来查找二叉树的高度，这是错误的，它未能通过测试用例，但是为什么它是错误的，如何从逻辑上证明这是错误的？

代码错误

public static int height(Node root) {
if(root != null){
if(root.left != null && root.right != null){   
return Math.max(height(root.left), height(root.right)) + 1;
}else if(root.left != null){
return height(root.left);  
}else{
return height(root.right);
} 
}
return 0;  
}

而下面的代码是正确的！！

正确的工作代码

public static int height(Node root) {
if(root != null){
if(root.left != null || root.right != null){   
return Math.max(height(root.left), height(root.right)) + 1;
}
}
return 0;  
}

两个代码之间的最大区别是什么，其中一个是正确的，另一个是错误的？

为清楚起见，此处添加了节点的类代码。

class Node {
Node left;
Node right;
int data;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}

这就是将节点插入二叉树的逻辑。

public static Node insert(Node root, int data) {
if(root == null) {
return new Node(data);
} else {
Node cur;
if(data <= root.data) {
cur = insert(root.left, data);
root.left = cur;
} else {
cur = insert(root.right, data);
root.right = cur;
}
return root;
}

Answer 1

在第二种和第三种情况下(只是一个左节点，或者只是一个右节点(，你不会添加一个来考虑你当前所在的节点。

顺便说一下，您的代码也存在潜在的错误，因为left和right都可能null。您的height函数可以处理null因此实际上不需要这些检查，除了对height函数本身的第一行进行检查。但是，如果在第二种情况下检查null很重要，那么在第三种情况下也应该检查null。