二叉樹常見面試題彙總

1.先序/中序/後序周遊二叉樹（遞歸非遞歸實作），層序周遊二叉樹周遊

2.求二叉樹的高度

size_t Height()//擷取該樹的高度
    {
        return _Height(_pRoot);
    }
    size_t _Height(Node* pRoot)//擷取數樹的深度，根節點為1
    {
        if(pRoot==NULL)
            return ;
        if(pRoot->_pLeft==NULL && pRoot->_pRight==NULL)
            return ;
        size_t LeftHeight = _Height(pRoot->_pLeft);
        size_t RightHeight = _Height(pRoot->_pRight);
        if(LeftHeight > RightHeight)
            return LeftHeight+;
        else
            return RightHeight+;
    }

3.葉子節點的個數

size_t GetLeefNode()//擷取葉子節點的個數(左子樹葉子節點加上右子樹的葉子節點)
    {
         return _GetLeefNode(_pRoot);
    }
    size_t _GetLeefNode(Node* pRoot)//擷取葉子節點的個數---遞歸左子樹葉子節點加上右子樹的葉子節點數
    {
        if(pRoot==NULL)
            return ;
        if(pRoot->_pLeft==NULL || pRoot->_pRight==NULL)
            return ;
        size_t pLeftLeefNode = _GetLeefNode(pRoot->_pLeft);
        size_t pRightLeefNode = _GetLeefNode(pRoot->_pRight);
        return pLeftLeefNode+pRightLeefNode;
    }

4.求第k層節點的個數

size_t GetKLevelNode(const size_t& k)//擷取第K層節點總數
    {
        return _GetKLevelNode(_pRoot,k);
    }

size_t _GetKLevelNode(Node* pRoot,size_t k)//擷取第k層節點個數--遞歸K-1層節點數
    {
        if(pRoot==NULL || k<= || k>_Height(pRoot))
            return ;
        if(k == )
            return ;
        size_t LeftKLevelNode = _GetKLevelNode(pRoot->_pLeft,k-);
        size_t RightKLevelNode = _GetKLevelNode(pRoot->_pRight,k-);
        return LeftKLevelNode+RightKLevelNode;
    }

2、3、4這三道常見面試題都是采用根據先序周遊的方法，來對節點進行遞歸操作

5.樹中兩個節點的最低公共祖先

思考分析：

該題根據題目給出的條件不同，将會有不同的簡便算法；

1>.該樹是二叉收索樹。

二叉收索樹的左孩子小于根節點，根節點小于右孩子，所以我們可以直接根據節點的值，對左右子樹進行判斷，進而得到結果

2>.該樹是普通樹，但有pParent指針。此時我們可以根據pPaent指針将該問題轉化為求相交兩個連結清單第一個相交的節點

3>.該樹是普通的樹，不含pParent指針

我們今天就介紹普通的樹，有三種得到最低公共祖先的方法

從根節點開始周遊節點，判斷所求節點是否在其左右子樹，若在，繼續向下周遊，否則，根節點就是它的雙親節點

缺點：重複周遊節點，時間開銷大

//樹中兩個節點的最低公共祖先(實作2---利用先序周遊每一個節點，并判斷兩個節點是否在該節點的左右分支上，在，則該節點即是最低公共祖先，否則，繼續周遊查找)
    Node* GetLastCommonParent2(Node* pNode1,Node* pNode2)
    {
        return _GetLastCommonParent2(_pRoot,pNode1,pNode2);
    }
    //樹中兩個節點的最低公共祖先---實作2(重複周遊節點并進行判斷，該方法的時間消耗大)
    Node* _GetLastCommonParent2(Node* pRoot,Node* pNode1,Node* pNode2)

    {
        if(pRoot==NULL || pNode1==NULL ||pNode2==NULL)
            return NULL;

        Node* pCur = NULL;
        if(IsFindNode(pRoot,pNode1) && IsFindNode(pRoot,pNode2))//若在根為pRoot的子樹中查找到pNode和pNode2，則繼續向下尋找，若找不到，二叉樹的根為最低祖先
        {
            if(pCur=_GetLastCommonParent2(pRoot->_pLeft,pNode1,pNode2))
                return pCur;
            if(pCur=_GetLastCommonParent2(pRoot->_pRight,pNode1,pNode2))
                return pCur;
            return pRoot;
        }
        return NULL;
    }

普通樹，用輔助記憶體棧實作，查找兩個棧中最後一個相同的元素

Node* _GetLastCommonParent1(Node* pRoot,Node* pNode1,Node* pNode2)
    {
        if(pRoot == NULL || pNode1==NULL || pNode2==NULL)
            return NULL;
        stack<Node*> s1;
        stack<Node*> s2;
        //調用查找該節點并儲存路徑的函數
        bool flags = false;
        FindNodeAndPush(pRoot,pNode1,s1,flags);
        flags = false;
        FindNodeAndPush(pRoot,pNode2,s2,flags);

        //進行出棧操作，找到最低公共祖先
        while(!s1.empty() && !s2.empty())
        {
            if(s1.size()>s2.size())
                s1.pop();
            else if(s1.size() < s2.size())
                s2.pop();
            else
            {
                while(s1.top() != s2.top())
                {
                    s1.pop();
                    s2.pop();
                }
                return s1.top();
            }
        }
        return NULL;
    }

    void FindNodeAndPush(Node* pRoot,Node* pNode,stack<Node*> &s,bool& flags)//從根節點開始查找該節點并儲存路徑到棧
    {
        if(pRoot==NULL || pNode == NULL)
            return;
        s.push(pRoot);
        if(pRoot == pNode)
        {
            flags = true;
            return;
        }
        if(!flags)
            FindNodeAndPush(pRoot->_pLeft,pNode,s,flags);
        if(!flags)
            FindNodeAndPush(pRoot->_pRight,pNode,s,flags);
        if(!flags)
        {
            s.pop();
            return;
        }
        return;
    }

利用輔助空間連結清單，将問題轉化為求兩個連結清單的最後一個相交的節點

Node* _GetLastCommonParent3(Node* pRoot,Node* pNode1,Node* pNode2)
    {
        if(pRoot==NULL || pNode1==NULL ||pNode2==NULL)
            return NULL;
        list<Node*> l1;
        list<Node*> l2;

        //從根節點開始查找節點并儲存路徑
        bool flags = false;
        FindNodeAndRemPath(pRoot,pNode1,l1,flags);
        flags = false;
        FindNodeAndRemPath(pRoot,pNode2,l2,flags);

        //求兩個相交連結清單中最後一個相交的節點
        return FindCrossPointOfTwoList(l1,l2);
    }

    void FindNodeAndRemPath(Node* pRoot,Node* pNode,list<Node*>& l,bool& flags)//從根節點開始查找節點并儲存路徑
    {
        if(pRoot==NULL)
            return;
        l.push_back(pRoot);
        if(pRoot == pNode)
        {
            flags = true;
            return;
        }
        if(!flags)
            FindNodeAndRemPath(pRoot->_pLeft,pNode,l,flags);
        if(!flags)
            FindNodeAndRemPath(pRoot->_pRight,pNode,l,flags);
        if(!flags)
        {
            l.pop_back();
            return;
        }
    }

    Node* FindCrossPointOfTwoList(list<Node*> l1,list<Node*> l2)//求兩個相交連結清單中最後一個相交的節點
    {
        //Node* pCur1 = l1.front();
        //Node* pCur2 = l2.front();
        list<Node*>::iterator it1 = l1.begin();
        list<Node*>::iterator it2 = l2.begin();
        Node* pCur = NULL;
        while(it1 != l1.end() && it2 != l2.end())
        {
            if(*it1 == *it2)
            {
                pCur = *it1;
                it1++;
                it2++;
            }
            else
            {
                return pCur;
            }
        }
        return NULL;
    }

6.求二叉樹的鏡像

先序周遊得到結果

//擷取一棵樹的鏡像---實作1（利用先序周遊）
    void GetMirrorTree1()
    {
        _pRoot = _GetMirrorTree1(_pRoot);
    }
    //擷取一棵樹的鏡像樹---先序周遊實作
    Node* _GetMirrorTree1(Node* pRoot)
    {
        if(pRoot == NULL || (pRoot->_pRight==NULL && pRoot->_pLeft==NULL))
            return NULL;
        std::swap(pRoot->_pLeft,pRoot->_pRight);
        Node* pCur = NULL;
        pCur = _GetMirrorTree(pRoot->_pLeft);
        pCur = _GetMirrorTree(pRoot->_pRight);
        return pRoot;
    }

層序周遊的到結果

//擷取一棵樹的鏡像---實作2（利用層序周遊）
    void GetMirrorTree2()
    {
        _pRoot = _GetMirrorTree2(_pRoot);
    }
//擷取一棵樹的鏡像樹---層序周遊實作
    Node* _GetMirrorTree2(Node* pRoot)
    {
        if(pRoot==NULL)
            return NULL;
        queue<Node*> q;
        q.push(pRoot);
        Node* pCur = NULL;
        while(!q.empty())
        {
            pCur=q.front();
            if(pCur->_pLeft!=NULL || pCur->_pRight!=NULL)
                std::swap(pCur->_pLeft,pCur->_pRight);
            q.pop();
            if(pCur->_pLeft!=NULL)
                q.push(pCur->_pLeft);
            if(pCur->_pRight!=NULL)
                q.push(pCur->_pRight);
        }
        return pRoot;
    }

7.判斷一棵樹是否為完全二叉樹

//判斷一棵樹是否為完全二叉樹
    bool IsCompleteTree()
    {
        return _IsCompleteTree(_pRoot);
    }
        bool _IsCompleteTree(Node* pRoot)//判斷一顆樹是不是完全二叉樹
    {
        //用一個隊列來儲存資料，從根節開始，通路他的左右子樹，若左右子樹都存在，則說明該樹有可能成為完全二叉樹,左右節點入棧
        //取隊列的頭節點，通路其左右子樹，若隻有左子樹存在，說明有可能是完全二叉樹，入棧繼續通路,此時該節點前面的節點都滿足
        //完全二叉樹的要求，若後面的節點有一個孩子節點，則說明該樹不是完全二叉樹；
        //若隻有右子樹存在，則節點沒有左子樹該樹一定不是完全二叉樹
        //若該節點沒有左右孩子，同隻有左孩子一樣，繼續通路後面的節點進行判斷
        if(pRoot==NULL)
            return true;
        queue<Node*> q;
        q.push(pRoot);
        Node* pCur = NULL;
        while(!q.empty())
        {
            pCur = q.front();
            if(pCur->_pLeft!=NULL && pCur->_pRight!=NULL)
            {
                q.push(pCur->_pLeft);
                q.push(pCur->_pRight);
            }
            else if(pCur->_pLeft!=NULL)
            {
                q.push(pCur->_pLeft);
                //判斷處理
                q.pop();
                while(!q.empty())
                {
                    pCur=q.front();
                    if(pCur->_pLeft!=NULL || pCur->_pRight!=NULL)
                        return false;
                    q.pop();
                }
            }
            else if(pCur->_pRight!=NULL)
            {
                return false;
            }
            else
            {
                //判斷處理
                q.pop();
                while(!q.empty())
                {
                    pCur=q.front();
                    if(pCur->_pLeft!=NULL || pCur->_pRight!=NULL)
                        return false;
                    q.pop();
                }
            }
            if(!q.empty())
            q.pop();
        }
        return true;
    }

8.用先序和中序清單重建二叉樹

void RebuildTree(char* preorder,char* inorder)//根據先序數列和中序數列重建二叉樹
    {
        if(preorder==NULL || inorder==NULL)
            return;
        size_t height1 = strlen(preorder);
        size_t height2 = strlen(inorder);
        size_t index = ;
        _pRoot = _RebuildTree(_pRoot,preorder,preorder+height1-,inorder,inorder+height2-,index);
    }
Node* _RebuildTree(Node* pRoot,char* pstart,char* pend,char* instart,char* inend,size_t& index)
    {
        if(pstart==NULL || pend==NULL || instart==NULL || inend==NULL)
            return NULL;
        if(instart>inend)
        {
            --index;
            return NULL;
        }
        pRoot = new Node;
        pRoot->_data = pstart[index];

        size_t idx=;
        for(idx=; idx<(inend-instart); ++idx)
        {
            if(pstart[index]==instart[idx])
                break;
        }

        pRoot->_pLeft = _RebuildTree(pRoot->_pLeft,pstart,pend,instart,instart+idx-,++index);
        pRoot->_pRight = _RebuildTree(pRoot->_pRight,pstart,pend,instart+idx+,inend,++index);
        return pRoot;
    }

9.根據中序和後序數列重建二叉樹

void RebuildTree2(char* inorder,char* postorder)//根據後序數列和中序數列重建二叉樹
    {
        if(inorder==NULL || postorder==NULL)
            return;
        size_t height1 = strlen(inorder);
        size_t height2 = strlen(postorder);
        if(height1 != height2)
            return;
        size_t index=height2-;
        _pRoot = _RebuildTree2(_pRoot,inorder,inorder+height1-,postorder,postorder+height2-,index);
    }
    //根據中序數列和後序數列重建二叉樹
    Node* _RebuildTree2(Node* pRoot,char* instart,char* inend,char* poststart,char* postend,size_t& index)
    {
        if(instart==NULL || inend==NULL || poststart==NULL || postend==NULL)
            return NULL;
        if(instart>inend)
        {
            ++index;
            return NULL;
        }

        pRoot = new Node;
        pRoot->_data = poststart[index];
        size_t idx=;
        for(; idx<(inend-instart); ++idx)
        {
            if(poststart[index]==instart[idx])
                break;
        }
        pRoot->_pRight = _RebuildTree2(pRoot->_pRight,instart+idx+,inend,poststart,postend,--index);
        pRoot->_pLeft = _RebuildTree2(pRoot->_pLeft,instart,instart+idx-,poststart,postend,--index);
        return pRoot;
    }

10.擷取一棵完全二叉樹所有節點的個數

普通周遊計數

缺點：需要周遊每個節點，時間開銷大

size_t GetAllNode(size_t& count)//利用先序周遊，查找每一個節點并計數，時間複雜度O(N),N是總的節點個數
    {
        return _GetAllNode(_pRoot,count);

    }
    size_t _GetAllNode(Node* pRoot,size_t& count)
    {
        if(pRoot==NULL)
            return count;

        if(pRoot!=NULL)
             ++count;
        count = _GetAllNode(pRoot->_pLeft,count);
        count = _GetAllNode(pRoot->_pRight,count);

    }

代碼優化：注意條件—完全二叉樹

//計算一棵完全二叉樹的所有節點的個數---優化，時間複雜度O(logN)2(平方)
    size_t GetAllNode1(size_t& count)
    {
        return _GetAllNode1(_pRoot,count);
    }

    size_t _GetAllNode1(Node* pRoot,size_t& count)
    {
        if(pRoot==NULL)
            return ;
        if(pRoot->_pLeft==NULL && pRoot->_pRight==NULL)
            return ;
        int h = GetHight(pRoot);//求深度O(logN)
        size_t ret = ;
        if((ret=GetHight(pRoot->_pRight)+)==h)//左子樹為滿二叉樹，用公式計算，右子樹周遊計算
        {
            count = ((<<(h-))-++_GetAllNode(pRoot->_pRight,count));//O(logN)
        }
        else
        {
            count = ((<<(h-))-++_GetAllNode(pRoot->_pLeft,count));//右子樹為滿二叉樹，用公式計算，左子樹周遊計算
        }
        return count;
    }
    size_t GetHight(Node* pRoot)//計算樹的最大深度
    {
        Node* pCur = pRoot;
        size_t ret=;
        while(pCur)
        {
            pCur = pCur->_pLeft;
            ret++;
        }
        return ret;
    }

11.判斷一棵樹是不是平衡二叉樹

普通解法—從根節點開始通路，判斷其左右子樹是否為平衡二叉樹，若不是，這直接退出，若是，繼續通路左右子樹

缺點：計算節點左右子樹高度時重複計算，多次通路，時間開銷大

bool IsBalanceTree1()//實作1---利用先序周遊的方法，但是節點重複周遊了，從根節點開始計算并比較每個子樹的深度
    {
        return _IsBalanceTree1(_pRoot);
    }
    bool _IsBalanceTree1(Node* pRoot)//判斷一棵樹是不是平衡二叉樹---實作1
    {
        //從根節點開始，得到左右子樹的高度，比較，若不滿足條件，則直接退出，後面再不用比較
        if(pRoot==NULL)
            return true;
        int left= _Height(pRoot->_pLeft);
        int right = _Height(pRoot->_pRight);
        int diff = left-right;
        if(diff> || diff<-)
            return false;
        return (_IsBalanceTree1(pRoot->_pLeft) && _IsBalanceTree1(pRoot->_pRight));
    }

利用後序周遊的方法實作對節點的通路

bool IsBalanceTree2()//實作二---利用後序周遊的方法，保證每個節點隻周遊一次，根據根節點的深度為左右子樹深度的最大值加一
    {
        int depth = ;
        return _IsBalanceTree2(_pRoot,depth);
    }
bool _IsBalanceTree2(Node* pRoot,int& depth)//判斷一棵樹是不是平衡二叉樹---實作2
    {
        //從樹的最左端的節點開始通路其左右子樹，這裡沒有調用_Height函數，最左端的節點的左子樹高度一定為1，最右端的右節點的深度也是1
        //再遞歸回退的過程中，得到節點左子樹的高度和右子樹的高度（下層高度+1），比較，若滿足條件，則繼續回退，得到目前層的高度，繼續比較上一層
        //若不滿足，則直接傳回錯誤
        if(pRoot==NULL)
        {
            depth = ;
            return true;
        }
        int left;
        int right;
        if(_IsBalanceTree2(pRoot->_pLeft,left)&&_IsBalanceTree2(pRoot->_pRight,right))
        {
            int diff = left-right;
            if(diff<= && diff>=-)
            {
                depth = +((left>right)? left:right);
                return true;
            }
            return false;
        }
        return false;
    }

二叉樹常見面試題彙總

繼續閱讀

FZU 1064 教授的測試

《劍指offer》學習筆記_面試題27_二叉樹的鏡像

LeetCode 102.二叉樹的層次周遊

計算二叉樹的高度（C++實作）

繩索資料結構（字元串快速拼接）

平衡二叉樹詳解筆記

真二叉樹重構(Proper Rebuild)

653. 兩數之和 IV - 輸入 BST653. 兩數之和 IV - 輸入 BST

(刷題筆記)Leetcode 653.兩數之和 IV - 輸入 BST題目解題思路代碼(C++)

【算法導論】堆排序一、數組轉換成堆二、如何進行堆排序三、堆排序過程四、堆排序時間複雜度

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

二叉樹的先序、中序、後序周遊總結

二叉樹及其應用--二叉樹建立

用JS模拟實作二叉樹(含周遊)

資料結構---二叉樹（手動建立及周遊）

樹的基本概念(定義、基本術語、性質)