程序員面試題精選100題(60)-判斷二叉樹是不是平衡[數據結構]

時間:2019-09-22 編輯:范文亭

題目:輸入一棵二叉樹的根結點,判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1,那么它就是一棵平衡二叉樹。例如下圖中的二叉樹就是一棵平衡二叉樹:

程序員面試題精選100題(60)-判斷二叉樹是不是平衡的 - 何海濤 - 微軟、Google等面試題

本系列博客的第27題,我們曾介紹過如何求二叉樹的深度。有了求二叉樹的深度的經驗之后再解決這個問題,我們很容易就能想到一個思路:在遍歷樹的每個結點的時候,調用函數TreeDepth得到它的左右子樹的深度。如果每個結點的左右子樹的深度相差都不超過1,按照定義它就是一棵平衡的二叉樹。這種思路對應的代碼如下:

bool IsBalanced(BinaryTreeNode* pRoot)

{

    if(pRoot == NULL)

        return true;

 

    int left = TreeDepth(pRoot->m_pLeft);

    int right = TreeDepth(pRoot->m_pRight);

    int diff = left - right;

    if(diff > 1 || diff < -1)

        return false;

 

    return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);

}

上面的代碼固然簡潔,但我們也要注意到由于一個節點會被重復遍歷多次,這種思路的時間效率不高。例如在函數IsBalance中輸入上圖中的二叉樹,首先判斷根結點(值為1的結點)的左右子樹是不是平衡結點。此時我們將往函數TreeDepth輸入左子樹根結點(值為2的結點),需要遍歷結點457。接下來判斷以值為2的結點為根結點的子樹是不是平衡樹的時候,仍然會遍歷結點457。毫無疑問,重復遍歷同一個結點會影響性能。接下來我們尋找不需要重復遍歷的算法。

如果我們用后序遍歷的方式遍歷二叉樹的每一個結點,在遍歷到一個結點之前我們已經遍歷了它的左右子樹。只要在遍歷每個結點的時候記錄它的深度(某一結點的深度等于它到葉節點的路徑的長度),我們就可以一邊遍歷一邊判斷每個結點是不是平衡的。下面是這種思路的參考代碼:

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)

{

    if(pRoot == NULL)

    {

        *pDepth = 0;

        return true;

    }

 

    int

本文已影響
相關文章
大亨pk10计划苹果版