先看问题描述：
/**
* Given a binary tree, determine if it is height-balanced.
* For this problem, a height-balanced binary tree is defined as a binary tree
* in which the depth of the two subtrees of every node never differ by more than 1.
*
*/
只要左右孩子节点的高度相差不到1，就可以认为这个二叉树是高度平衡二叉树。
判断数的高度，自然要用到递归。
public class BalancedBinaryTree {
public static boolean isBalanced(TreeNode root) {
return determine(root) >= 0 ? true : false;
}
private static int determine(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftDepth = determine(root.left);
int rightDepth = determine(root.right);
if (leftDepth < 0 || rightDepth < 0|| Math.abs(leftDepth - rightDepth) > 1)
return -1;
return Math.max(leftDepth, rightDepth) + 1;
}
}
public static void main(String arg[])
{
TreeNode r1 = new TreeNode(1);
TreeNode r2 = new TreeNode(2);
TreeNode r3 = new TreeNode(3);
TreeNode r4 = new TreeNode(4);
TreeNode r5 = new TreeNode(5);
TreeNode r6 = new TreeNode(6);
r1.left = r2;
r1.right = r3;
r2.left = r4;
r2.right = r5;
r3.right = r6;
if(isBalanced(r1))
{
System.out.print("is a height-balanced tree");
}
else{
System.out.print("is not a height-balanced tree");
}
}
}
二叉树节点定义：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x)
{
val = x;
}
}上面代码中，determine返回的为正值则表示是高度平衡二叉树。初始化二叉树时简单处理了，比较方便看。