剑指Offer-37 判断平衡树（后序遍历）

平衡二叉树（Balanced Binary Tree）又被称为AVL树,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

image.png

问题：输入一棵二叉树，判断该二叉树是否是平衡二叉树。(不考虑节点大小关系，只考虑树是否平衡)

自上而下分析

重点是判断左右子树的高度，比较差的绝对值是否大于1,如果大于1则不是AVL树。对于二叉树高度问题可参考二叉树高度解法

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        // 左右子树高度差不大于1
        if(root == null) return true;
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) return false;
        // 如果遇到了叶子节点
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    // 非递归写法
    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 1, depth = 0;
        while (queue.size() != 0) {
            count--;
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (count == 0) {
                depth++;
                count = queue.size();
            }
        }
        return depth;
    }
}

这个解法有一个问题，基于广度优先遍历。每次判断节点是否符合规则，都需要去层次遍历子树。会存在大量的冗余。

自下而上分析

使用基于后序遍历算法，如果子树满足二叉树则返回高度，否则返回false。这样的话遍历一遍既可以完成判断。

public class Solution {
     public boolean IsBalanced_Solution(TreeNode root) {
        // 返回-1 说明不是AVL数。
        return getDepth(root) != -1;
    }

    // 后序遍历（递归）
    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        int left = getDepth(root.left);
        if ( left == -1 ) return -1;// 如果左子树不是平衡树，则整个树不是AVL树，可以简化遍历
        int right = getDepth(root.right);
        if ( right == -1 ) return -1;

        //if (left == -1 || right == -1) return -1; 把整个判断提前
        // 如果该树是平衡树返回树的高度，否则返回-1
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }
}

AVL树很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。