描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

思路

先一个节点一个节点的判断其是否满足平衡二叉树。如果满足就接着判断其左右孩子是否也是平衡二叉树。

注：在计算左右孩子的深度时，用链表存储从根节点到每个叶子节点的深度，最后取出最大的值，就是该节点的深度。

代码

得到节点的深度

//得到一个节点的深度集合ArrayList
    public void sum(TreeNode root,int count,ArrayList res){
        count++;
        if(root.left != null){
           sum(root.left,count,res);
        }
        if(root.right != null){
          sum(root.right,count,res);
        }
        res.add(count);
        return;
        
    }

判断是不是平衡二叉树

  //判断以该节点root为根节点的二叉树，是否为平衡二叉树
    public boolean isBa(TreeNode root){
        ArrayList<Integer> resLift = new ArrayList<>();
        ArrayList<Integer> resRight = new ArrayList<>();
        int countLift = 0;
        int countRight = 0;
        if(root.left == null){
            countLift = 0;
        }else{
            sum(root.left,countLift,resLift);
            Collections.sort(resLift);
           countLift = resLift.get(resLift.size()-1);
        }
        if(root.right == null){
            countRight = 0;
        }else{
            sum(root.right,countRight,resRight);
            Collections.sort(resRight);
            countRight = resRight.get(resRight.size() -1);
        }
        return countLift - countRight <= 1 && countLift - countRight>=-1;
    }

 整体代码

import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        
        if(root ==null){
            return true;
        }
        //先判断根节点是否为平衡二叉树，是接接着遍历左右孩子节点
        if(!isBa(root)){
            return false;
        }else{
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }
    }
    
    //判断以该节点root为根节点的二叉树，是否为平衡二叉树
    public boolean isBa(TreeNode root){
        ArrayList<Integer> resLift = new ArrayList<>();
        ArrayList<Integer> resRight = new ArrayList<>();
        int countLift = 0;
        int countRight = 0;
        if(root.left == null){
            countLift = 0;
        }else{
            sum(root.left,countLift,resLift);
            Collections.sort(resLift);
           countLift = resLift.get(resLift.size()-1);
        }
        if(root.right == null){
            countRight = 0;
        }else{
            sum(root.right,countRight,resRight);
            Collections.sort(resRight);
            countRight = resRight.get(resRight.size() -1);
        }
        return countLift - countRight <= 1 && countLift - countRight>=-1;
    }
    
    //得到一个节点的深度集合ArrayList
    public void sum(TreeNode root,int count,ArrayList res){
        count++;
        if(root.left != null){
           sum(root.left,count,res);
        }
        if(root.right != null){
          sum(root.right,count,res);
        }
        res.add(count);
        return;
        
    }
}