子树
image.png
平衡二叉树
image.png
判断是否为平衡二叉树
- 在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差不超过1，按照定义它就是一棵平衡的二叉树。显然，我们会因此遍历多次二叉树，因此不推荐这种方法。
/**
* ★缺点：该方法在求该结点的的左右子树深度时遍历一遍树，
* 再次判断子树的平衡性时又遍历一遍树结构，造成遍历多次。
* ★不推荐
* @param head
* @return
*/
public static boolean isBalanceRecursive(Node head){
if (head == null)
return true;
int nleft = treeDepth(head.left);
int nright = treeDepth(head.right);
int differ = nleft - nright;
if(differ > 1 || differ < -1)
return false;
return isBalanceRecursive(head.left) && isBalanceRecursive(head.right);
}
public static int treeDepth(Node head){
if (head == null)
return 0;
int leftDepth = treeDepth(head.left);
int rightDepth = treeDepth(head.right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
- 如果我们用后序遍历的方式遍历二叉树的每个结点，在遍历一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候我们记录它的深度（某一节点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡二叉树。
/**
* 为了在一次遍历中判断二叉树的平衡性，采用后序遍历是一个不错的想法。
* @param head
* @return
*/
public static boolean isBalance(Node head){
return isBalance(head, 0);
}
public static boolean isBalance(Node head, int depth){
if(head == null){
depth = 0;
return true;
}
int left = 0, right = 0;
if (isBalance(head.left, left) && isBalance(head.right, right)){
int diff = left - right;
if(diff <= 1 && diff >= -1){
depth = left > right ? left + 1 : right + 1;
return true;
}
}
return false;
}
