平衡二叉树【Java数据结构】

判断是否为平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例1：

输入：root = [3,9,20,null,null,15,7] 输出：true 

示例2：

输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

分析：

首先我们需要定义一个maxDepth方法来判断找出左右子树的高度：

public int maxDepth(TreeNode root) {
         if(root == null) {
             return 0;
         }
         int leftHeight = maxDepth(root.left);
         int rightHeight = maxDepth(root.right);
         return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
 }

1.首先对头结点的左子树进行高度判断，得出结果1：

2.对头结点的右子树进行高度判断，得出结果2：

3.通过比较左右子树的高度，得出该树的最大高度。

得到左右子树的高度后，就可以来判断是否为平衡树：

由题目可以看出，每一棵子树的左右子树之间的高度差都不可以超过1，所以我们可以用递归思想来判断每一棵子树的左右子树之间的高度差是否超过1，只要有，就可以直接返回false来结束递归。 整体思路：先求当前root节点是不是平衡的。 再去判断左树是不是平衡的。 再去判断右树是不是平衡的。

public boolean isBalanced(TreeNode root) {
         if(root == null){
             return true;
         }
         int leftH = maxDepth(root.left);
         int rightH = maxDepth(root.right);

         return Math.abs(leftH-rightH )<= 1 && isBalanced(root.left) && isBalanced(root.right);
     }

但这种解法的时间复杂度为O(n^2)（在最坏的情况下，一个平衡树的每一个节点的高度都要求一次），效率就没那么高。

优化：

例如下图这种情况，在第一次判断的时候，1的左子树和右子树的高度是都是3，符合题意，但此时2的左子树和右子树就不形成平衡树了，但是此时不会判断出来，而程序继续执行才会判断出来，这就降低了效率，所以我们可以从此问题出发，在计算树的高度的时候，就进行判断每一个节点的左右子树是否违反平衡树的构成条件，也就是左右子树的高度差绝对值不超过1，如果是，就可以直接返回-1，这样就大大提高的效率。

public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        if(leftHeight>=0 && rightHeight>=0 && Math.abs(leftHeight-rightHeight)<=1){    //1
            return Math.max(leftHeight,rightHeight) + 1;
        }else{
            return -1;    
        }
    }
    public boolean isBalanced(TreeNode root){
        if(root == null){
            return true;
        }
        return maxDepth(root)>=0;            //非平衡树只会返回-1！！！
    }

此处有个注意点 :1处if的判断条件里leftHeight>=0 && rightHeight>=0 是因为如果左子树的返回值为-1，此时已经不是平衡树了，而右子树如果为空，返回0，-1-0的绝对值为1，这就改变了结果。