判断树是否是AVL

方法一（不推荐）

    /**
     * 判断树是否是 AVL
     * 方法一:
     * 首先判断当前节点是否平衡(计算左右子树的高度)，然后前序遍历所有的节点，判断每个节点是否平衡
     * <p>
     * 缺点：计算当前节点的高度时，左右子树都全部被遍历了一遍。再判断左子节点是否平衡，计算高度，又会将左子节点的左子树右子树遍历一遍
     * 导致大量节点重复遍历
     *
     * @param root
     * @return
     */
    public boolean isAVL(TreeNode root) {

        if (root == null) return true;

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        boolean flag = true;
        if (Math.abs(leftHeight - rightHeight) > 1) {
            flag = false;
        }
        return flag && isAVL(root.left) && isAVL(root.right);
    }


    /**
     * 获得以root 为根节点的树的高
     * 计算左子树的高和右子树的高
     * 再计算当前节点的高
     * 后序计算
     *
     * @param root
     * @return
     */
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

方法二（推荐）

  /**
     * 方法二：在判断根节点是否平衡时，计算左右子树高度时，遍历到每个节点时都判断当前节点是否平衡，只要有一个不平衡，就直接返回false
     * <p>
     * 只要遍历一次树
     *
     * @param root
     * @return
     */
    public boolean isBalance(TreeNode root) {

        boolean[] isBalance = new boolean[1];
        isBalance[0] = true;

        getHeight(root, isBalance);

        return isBalance[0];

    }

    /**
     * 既计算节点 root 的高度，同时也要判断节点 root 是否平衡
     *
     * @param root
     * @param isBalance
     * @return
     */
    public int getHeight(TreeNode root, boolean[] isBalance) {
        if (root == null) return 0;

        int leftHeight = getHeight(root.left, isBalance);
        if (!isBalance[0]) return -1; // 左子树不平衡，直接返回，不用计算当前节点的高度了
        int rightHeight = getHeight(root.right, isBalance);
        if (!isBalance[0]) return -1; // 右子树不平衡，直接返回，不用计算当前节点的高度了

        if (Math.abs(leftHeight - rightHeight) > 1) {
            isBalance[0] = false;
            return -1;
        }

        // 只有左右子树平衡了，才返回高度
        return 1 + Math.max(leftHeight, rightHeight);

    }