寻找二叉树的高度

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

在第二种和第三种情况下（只是一个左边的节点，或者只是一个右边的节点），你并没有增加一个占你当前所在的节点。

对了，你的代码也有一个潜在的bug，就是有可能两个 left 和 right 将要 null. 您的 height 函数可以处理 null 所以其实这些检查都是不必要的，除了第一行的检查。height 函数本身。但如果重要的是要检查 null 在第二种情况下，那么你应该检查是否有 null 在第三种情况下也是如此。