剑指offer第三十九题。

题目描述

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

解题思路

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

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}
}