求二叉树的高度

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;  
}

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

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

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在第三种情况下检查。