|
采用后序遍历的方法（关于树的相关算法多考虑前序、中序、后序、深度优先、广度优先算法，试图找到与题目之间的关系）。
通过后序遍历的方式，在遍历的过程中记录每个节点的深度，然后父节点通过子节点的深度，算出自己的深度，当左右子树的深度之差的绝对值大于1时，跳出循环，否则继续比较。
public boolean isBalanced(TreeNode *pRoot,int *pdepth){
if(pRoot==null)
{
*pdepth=0;
return true;
}
int *left,*right;
if(isBalanced(pRoot->left,left)&&isBalanced(pRoot->right,right))
{
int sub=*left-*right;
if(sub>=-1&&sub<=1)
{
*pdepth=max(*left,*right)+1;
return true;
}
}
return false;
}
|
|
|
