其實(shí)關(guān)于樹(shù)的好多題都是遞歸的。。

首先復(fù)習(xí)一下什么是平衡樹(shù)：

平衡二叉樹(shù)

即：所有節(jié)點(diǎn)的左右子樹(shù)的高度差不超過(guò)1

思路之一：
求每個(gè)節(jié)點(diǎn)的高度
假設(shè)我們有一個(gè)getTreeDepth(TreeNode* tree )的函數(shù)
然后這樣：

bool IsBalanced(TreeNode* tree)
{
    if (tree == NULL)
        return 1;
    
    int leftHigh = getTreeDepth(tree->left);
    int rightHigh = getTreeDepth(tree->right);
    if (leftHigh - rightHigh > 1 || leftHigh - rightHigh < -1)
        return false;
    return IsBalanced(tree->left) && IsBalanced(tree->right);

}

但是呢，這個(gè)方法有一個(gè)老問(wèn)題，就是普通的遞歸求Fibnacci數(shù)列的直接調(diào)用f(n)=f(n-1)+f(n-2)這個(gè)函數(shù)會(huì)導(dǎo)致大量的重復(fù)計(jì)算，上面這個(gè)函數(shù)也是這樣，我們從根節(jié)點(diǎn)開(kāi)始算depth也是遍歷了很多次，所以我們稍稍改進(jìn)一下：

bool IsBalanced(TreeNode* tree, int* depth)
{
    if (tree == NULL)
    {
        *depth = 0;
        return true;
    }
    int left, right;
    if (IsBalanced(tree->left, &left) && IsBalanced(tree->right, &right))
    {
        int diff = left - right;
        if (diff >= -1 && diff <= 1)
        {
            *depth = (left > right ? left : right) + 1;
            return true;
        }

    }
    return false;
}

bool IsBalanced(TreeNode* tree)
{
    int depth = 0;
    return IsBalanced(tree, &depth);
}

其實(shí)思路是差不多的，只是通過(guò)遞歸的方法，從最下面開(kāi)始計(jì)算。

同樣的思路也可以求路徑長(zhǎng)呢。

文章參考何海濤大神文章