1 什么是平衡二叉树？
左子树和右子树的高度不能超过1 的书就叫平衡二叉树。
2 解题思路
先序遍历 ,获取左子树的高度和 获取右子树的高度 然后比较高度差 ,如何高度大于1 返回flase，否则返回true，并递归该过程。
3 代码实现
/**
* 判断一个树是否为平衡二叉树
* @author Administrator
*
*/
public class Code_06_IsBalancedTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isBalance(Node head) {
boolean[] res = new boolean[1];
res[0] = true;
getHeight(head, 1, res);
return res[0];
}
/**
* 先序遍历 平衡二叉树 左右子树高度相差不超过1
* @param head
* @param level
* @param res
* @return
*/
public static int getHeight(Node head, int level, boolean[] res) {
if (head == null) {
return level;
}
int lH = getHeight(head.left, level + 1, res);//左子树的高度
if (!res[0]) {
return level;
}
int rH = getHeight(head.right, level + 1, res);//右子树高度
if (!res[0]) {
return level;
}
if (Math.abs(lH - rH) > 1) {//左右子树高度差值
res[0] = false;
}
return Math.max(lH, rH);
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
// head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
// head.right.left = new Node(6);
// head.right.right = new Node(7);
System.out.println(isBalance(head));
}
}
