算法思路:先编写一个计算二叉树深度的函数GetDepth,利用递归实现;然后再递归判断每个节点的左右子树的深度是否相差1
static int GetDepth(BinNode root)
{
if (root == null)
return 0;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
return (leftLength > rightLength
leftLength : rightLength) + 1;
}
注意这里的+1,对应于root不为空(算作当前1个深度)
static bool IsBalanceTree(BinNode root)
{
if (root == null)
return true;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
int distance = leftLength > rightLength
leftLength - rightLength : rightLength -leftLength;
if (distance > 1)
return false;
else
return IsBalanceTree(root.Left) && IsBalanceTree(root.Right);
}
上述程序的逻辑是,只要当前节点root的Left和Right深度差不超过1,就递归判断Left和Right是否也符合条件,直到为Left或Right为null,这意味着它们的深度为0,能走到这一步,前面必然都符合条件,所以整个二叉树都符合条件。