《程序员面试金典》中的一道题
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
我是用java通过的
这是树节点的定义：
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
思路：
要想判定平衡二叉树是否成立，关键在于其左右节点的高度相差是否小于等于1 ；
所以定义一个求每个节点高度的方法
采用递归
public int height(TreeNode root, int h){
if (root ==null)
return 0 ;
int l = height(root.left , h); //获得当前节点的左节点的高度
int r = height(root.right , h); //获取当前节点的右节点的高度
h = (l > r ? l : r)+1 ; //找出最大高度+1
return h;
}
高度的问题解决了，现在就剩下比较每个节点的左右节点的高度了
依旧是采用递归方式
public boolean isBalance(TreeNode root) {
if (root ==null)
return true ;
int h =0 ;
int l =0 ;
h = height(root.left , h);
l = height(root.right , l);
if (h-l<-1 || h-l >1)
return false ;
return isBalance(root.left) && isBalance(root.right);
}
