博客

110. 平衡二叉树

。这道题与

剑指 Offer 55 – II. 平衡二叉树

属于同一道题。

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

简单难度

这道题采用分治算法即可。所谓分治（Divide and Conquer）算法，就是先分别处理局部，再合并结果，分(divide)阶段将问题分成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”合并”在一起，即分而治之。

这里，我们首先递归到每个叶子节点，就是拆分，然后再返回，合并的时候再判断子树是否平衡，也就是左右子树的高度差是否大于1，如果有一个子树的两边节点高度差大于1，那么就是不平衡了。

这里使用小于0的-1表示不平衡，如果出现了-1，那么就一直返回-1，否则对当前树的高度取最大的子树高度+1，继续向上合并。

最后递归结束时，如果值小于0，那么就是不平衡的。

public boolean isBalanced( TreeNode root ){

   return depth( root ) >= 0;
}

public int depth( TreeNode root ){

   if( root == null ){
      return 0;
   }
   /*分 拆解*/
   int left = depth( root.left );
   int right = depth( root.right );
   /*治 合并*/
   //-1 表示不平衡
   //如果左右子树的深度绝对值差大于1，就说明不平衡。
   if( left < 0 || right < 0 || Math.abs( left - right ) > 1 ){
      return -1;
   }
   else{
      //左右子树的深度绝对值差不大于1，就说明平衡，那么返回当前树的最大高度
      return Math.max( left, right ) + 1;
   }
}

另一种简单的方法是使用一个全局标志位flag。

private boolean flag = true;

public boolean isBalanced(TreeNode root) {

    depth(root);
    return flag;
}

int depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = depth(root.left);
    int right = depth(root.right);
    if (Math.abs(left - right) > 1) {
        flag = false;
    }
    return Math.max(left, right) + 1;
}