792
檢查一個二叉樹是否平衡的算法分析與C++實現
今天麵試一個實習生，就想既然是未出校園，那就出一個比較基礎的題吧，沒想到答的並不如人意，對於樹的操作完全不熟悉，因此此題算是未作答。原來我想看一下他分析問題的思路，優化代碼的能力。接下來會把最近半年我出的麵試題整理出來，以來share給其它同事，而來算是自己校園記憶的一個總結，畢竟自己在項目中已經很久未用到這些知識。其實很多題目都是來源於CareerCup.com。這上麵匯集了許多IT名企的麵試筆試題目，非常值得找工作的人學習。
言歸正傳，什麼是二叉樹是否平衡的定義，如果麵試者不知道，那肯定要提出來，而不是簡簡單單說我對樹不熟悉，或者找其他更多更多的理由。
其實可以根據平衡的定義，直接遞歸訪問整棵樹，計算子樹的高度。
struct TreeNode{
TreeNode *leftChild;
TreeNode *rightChild;
int data;
};
int getHeight(const TreeNode* root){
if( root == nullptr){
return 0;
}
return max(getHeight(root->leftChild), getHeight(root->rightChild)) + 1;
}
bool isBalanced(const TreeNode* root){
if( root == nullptr){
return true;
}
int heightDiff = abs(getHeight(root->leftChild) - getHeight(root->rightChild));
if( heightDiff > 1){
return false;
}
else{
return isBalanced(root->leftChild) && isBalanced(root->rightChild);
}
}如果開始能給出這個解法那是可以接受的。但是，由於同一個node的高度會被重複計算，因此效率不高。算法複雜度是O(n*logn)。接下來，我們要改進這個算法，使得子樹的高度不再重複計算：我們通過刪減重複的getHeight(const TreeNode*)調用。其實getHeight不單可以計算子樹的高度，其實還可以判斷子樹是否的平衡的，如果不平衡怎麼辦？直接返回-1。那該遞歸調用就可以結束了。
因此，改進的算法就是從root開始遞歸檢查每個子樹的高度，如果子樹是平衡的，那麼就返回子樹的高度，否則返回-1：遞歸結束，樹是不平衡的。
int checkHeight(const TreeNode* root){
if( root == nullptr){
return 0;
}
// check the left subtree is balanced or not.
int leftHeight = checkHeight(root->leftChild);
if( leftHeight == -1 ){
return -1;
}
// check the right subtree is balanced or not.
int rightHeight = checkHeight(root->rightChild);
if( rightHeight == -1){
return -1;
}
// check the current tree is balanced or not.
int diff = leftHeight - rightHeight;
if( abs(diff) > 1){
return -1;
}
else{
// return the tree height.
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(const TreeNode* root){
return ( checkHeight(root) == -1 )? false:true;
}
由於每個node隻會訪問一次，因此算法時間複雜度為O(n)。但是需要額外的O(logn)的空間。
最後更新：2017-04-03 12:53:59