查找二叉树的高度

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 代码。

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，因此 none 这个检查确实是必要的，除了对 height 函数本身的第一行的检查。但是，如果在第二种情况下检查 null 很重要，那么您也应该在第三种情况下检查 null。

查找二叉树的高度

Finding the height of a binary tree

java

algorithm

tree

binary-tree

data-structures