程序员面试题精选100题（60）-判断二叉树是不是平衡[数据结构] (2)

    if(IsBalanced(pRoot->m_pLeft, &left)

        && IsBalanced(pRoot->m_pRight, &right))

    {

        int diff = left - right;

        if(diff <= 1 && diff >= -1)

        {

            *pDepth = 1 + (left > right ? left : right);

            return true;

        }

    }

    return false;

}

我们只需要给上面的函数传入二叉树的根结点以及一个表示结点深度的整形变量就可以了：

bool IsBalanced(BinaryTreeNode* pRoot)

{

    int depth = 0;

    return IsBalanced(pRoot, &depth);

}

在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树了。