java - 如何修复决定树是否平衡树的方法？

Question

例如，我有一棵树:

                              8
                            _   _
                           /     \ 
                         1       48
                        /       /  \
                       0       40   50
                              /
                             10

当我向 TREE 添加 10 时，我的方法确定该 AVL 树不是 AVL 树，并尝试平衡它。我不明白为什么 isAVLTree 方法不起作用。

public static boolean isAVLTree(Root root) {
        return (findMaxDepth(root) - findMinDepth(root)) <= 1;
    }

public static int findMaxDepth(Root root) {
        if (root == null ) {
            return 0;
        }
        return 1 + Math.max(findMaxDepth(root.leftSide), findMaxDepth(root.rightSide));
    }

 public static int findMinDepth(Root root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.min(findMinDepth(root.leftSide), findMinDepth(root.rightSide));
}

目前方法isAVLTree返回false，因为

(findMaxDepth(root) - findMinDepth(root)) <= 1
((         4        -        2)           <= 1 )   ->>>>>>>>>>>>>> FALSE

Answer 1

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

( AVL Tree )

这不是您在 isAVLTree 方法中实现的。最大深度和最小深度之间的差异不必 <= 1。

相反，你应该要求左右子树都是AVL树，并且左右子树的高度差<= 1。

public static boolean isAVLTree(Root root) 
{
    if (root == null) {
        return true;
    }

    return Math.abs(findMaxDepth(root.leftSide) - findMaxDepth(root.rightSide)) <= 1 &&
        isAVLTree (root.rightSide) &&
        isAVLTree (root.leftSide);
}