检查树是否平衡时出现断言错误

Question

我有一棵二叉树，想检查这棵树是否平衡。我有以下代码：

public boolean isBalanced(){
        return balanced(root);
    }

    public boolean balanced(Node current){
        int leftHeight;

        int rightHeight;

        if(current == null){
            return true;
        }
        leftHeight = height(current.left);
        rightHeight = height(current.right);

        if(leftHeight - rightHeight <= 1){
            return true;
        }

        return false;
    }

    int height(Node node) 
    { 
        /* base case tree is empty */
        if (node == null) 
            return 0; 

        /* If tree is not empty then height = 1 + max of left 
         height and right heights */
        return 1 + Math.max(height(node.left), height(node.right)); 
    }

测试给出了错误 java.lang.AssertionError 但没有提供更多详细信息。我不知道那个错误是从哪里来的。

Answer 1

根据wikipedia，平衡二叉树的定义是A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

在您的代码中，您正在检查

if(leftHeight - rightHeight <= 1){
      return true;
}

如果 leftHeight = 0 和 rightHeight=2 怎么办？您的代码将 return 与 (0-2) = -2 and -2 <= 1 一样。你应该检查左子树高度和右子树高度之间的绝对差值。

检查树是否平衡时出现断言错误

Assertion Error while checking if Tree is balanced

java

binary-tree

binary-search-tree

data-structures