【面试题39-平衡二叉树】

剑指offer第三十九题。

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

首先明确平衡二叉树的概念，就是数的最大高度和最小高度差不超过1.根据上一题我们得到灵感，我们可以分别求出左右子树的最大深度，然后对他们两进行比较即可。

我的答案

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        
        if(root.left == null && root.right == null){
            return true;
        }
        
        //获取左右子树的最大高度
        int left = judge(root.left);
        int right = judge(root.right);
        
        //两边高度不超过1即可
        return Math.abs(left-right) <= 1;
    }
    
    private int judge(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = judge(root.left);
        int right = judge(root.right);
        
        return Math.max(left,right) + 1;
    }
}