题解 | #判断是不是平衡二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    //计算树的深度
    public int deep(TreeNode node){
        if(node==null){
            return 0;
        }
        int left = deep(node.left);
        int right = deep(node.right);
        //返回左右子树中的较大深度加上当前节点给增加的深度是1
        return left > right ? left+1 : right+1;
    }
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        if(pRoot==null){
            return true;
        }
        //求当前树的左右深度
        int left = deep(pRoot.left);
        int right = deep(pRoot.right);
        //左右深度相差大于一则非平衡树
        if(left - right > 1 || right - left > 1){
            return false;
        }
        //遍历左右子树，当且仅当都为平衡二叉树时，本树才是平衡的
        return IsBalanced_Solution(pRoot.left)&&IsBalanced_Solution(pRoot.right);
    }
}

方法：递归

平衡二叉树的所有子树都是平衡的，左右深度之差都相差不超过一。因此既要判断整个树，又要判断每个子树，很适合用递归。为了方便算深度，定义了一个专门计算深度的函数。方法也很简单，空节点返回0，向下递归分别返回左右深度，返回值为左右深度中的较大值加上本节点占用的一层深度。

步骤：

1、空树返回真

2、计算左右深度

3、判断相差是否大于一

4、遍历左右子树，当且仅当都为平衡二叉树时，本树才是平衡的