判斷一棵二叉樹是否平衡

注：算法引自《程式員面試白皮書》。

/*
* 二叉樹平衡的定義：
* 一棵二叉樹是平衡的，當且僅當左右兩棵子樹的高度差的絕對值不超過1，
* 并且左右兩棵子樹都是一棵平衡二叉樹。
* 同時，空樹是一棵平衡二叉樹。
*/

/*
* 計算樹高度的子函數也可遞歸實作。
* 首先，考慮遞歸的出口：當node為空時，高度為0.
* 其次，當node不為空，這棵樹的高度為左右子樹中的高度較高者加1.
*/
template < typename T >
int level( TreeNode< T >* root )
{
    if ( root == nullptr )
    {
        return ;
    }
    return max( level( root->left ), level( root->right ) ) + ;
}

// 判斷高度差的絕對值不超過1，以及遞歸左右子樹都為平衡二叉樹
template < typename T >
bool isBanlanced( TreeNode< T >* root )
{
    if ( root == nullptr )
    {
        return true;
    }

    int factor = abs( level( root->left ) - level( root->right ) );
    return factor <  && isBalanced( root->left ) && isBalanced( root->right );
}