檢查一個二叉樹是否平衡的算法分析與C++實作

今天面試一個實習生，就想既然是未出校園，那就出一個比較基礎的題吧，沒想到答的并不如人意，對于樹的操作完全不熟悉，是以此題算是未作答。原來我想看一下他分析問題的思路，優化代碼的能力。接下來會把最近半年我出的面試題整理出來，以來share給其它同僚，而來算是自己校園記憶的一個總結，畢竟自己在項目中已經很久未用到這些知識。其實很多題目都是來源于careercup.com。這上面彙集了許多it名企的面試筆試題目，非常值得找工作的人學習。

言歸正傳，什麼是二叉樹是否平衡的定義，如果面試者不知道，那肯定要提出來，而不是簡簡單單說我對樹不熟悉，或者找其他更多更多的理由。

其實可以根據平衡的定義，直接遞歸通路整棵樹，計算子樹的高度。

如果開始能給出這個解法那是可以接受的。但是，由于同一個node的高度會被重複計算，是以效率不高。算法複雜度是o(n*logn)。接下來，我們要改進這個算法，使得子樹的高度不再重複計算：我們通過删減重複的getheight(const treenode*)調用。其實getheight不單可以計算子樹的高度，其實還可以判斷子樹是否的平衡的，如果不平衡怎麼辦？直接傳回-1。那該遞歸調用就可以結束了。

是以，改進的算法就是從root開始遞歸檢查每個子樹的高度，如果子樹是平衡的，那麼就傳回子樹的高度，否則傳回-1：遞歸結束，樹是不平衡的。

由于每個node隻會通路一次，是以算法時間複雜度為o(n)。但是需要額外的o(logn)的空間。