版權全部，轉載請注明出處，謝謝！
http://blog.csdn.net/walkinginthewind/article/details/7518888
樹是一種比較重要的數據結構，尤其是二叉樹。二叉樹是一種特殊的樹，在二叉樹中每一個節點最多有兩個子節點，一般稱為左子節點和右子節點（或左孩子和右孩子），而且二叉樹的子樹有左右之分，其次序不能隨意顛倒。二叉樹是遞歸定義的，因此，與二叉樹有關的題目基本都能夠用遞歸思想解決，當然有些題目非遞歸解法也應該掌握，如非遞歸遍歷節點等等。本文努力對二叉樹相關題目做一個較全的整理總結，希望對找工作的同學有所幫助。
二叉樹節點定義例如以下：
struct BinaryTreeNode
{
? ? int m_nValue;
? ? BinaryTreeNode* m_pLeft;
? ? BinaryTreeNode* m_pRight;
};
相關鏈接：
輕松搞定面試中的鏈表題目
題目列表：
1. 求二叉樹中的節點個數
2. 求二叉樹的深度
3. 前序遍歷，中序遍歷，后序遍歷
4.分層遍歷二叉樹（按層次從上往下，從左往右）
5. 將二叉查找樹變為有序的雙向鏈表
6. 求二叉樹第K層的節點個數
7. 求二叉樹中葉子節點的個數
8. 推斷兩棵二叉樹是否結構同樣
9. 推斷二叉樹是不是平衡二叉樹
10. 求二叉樹的鏡像
11. 求二叉樹中兩個節點的最低公共祖先節點
12. 求二叉樹中節點的最大距離
13. 由前序遍歷序列和中序遍歷序列重建二叉樹
14.推斷二叉樹是不是全然二叉樹
具體解答
1. 求二叉樹中的節點個數
遞歸解法：
（1）假設二叉樹為空，節點個數為0
（2）假設二叉樹不為空，二叉樹節點個數 = 左子樹節點個數 + 右子樹節點個數 + 1
參考代碼例如以下：
int GetNodeNum(BinaryTreeNode * pRoot)
{if(pRoot == NULL) // 遞歸出口return 0;return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;
}遞歸解法：
（1）假設二叉樹為空，二叉樹的深度為0
（2）假設二叉樹不為空，二叉樹的深度 = max(左子樹深度， 右子樹深度) + 1
參考代碼例如以下：
int GetDepth(BinaryTreeNode * pRoot)
{if(pRoot == NULL) // 遞歸出口return 0;int depthLeft = GetDepth(pRoot->m_pLeft);int depthRight = GetDepth(pRoot->m_pRight);return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);
}前序遍歷遞歸解法：
（1）假設二叉樹為空，空操作
（2）假設二叉樹不為空，訪問根節點，前序遍歷左子樹，前序遍歷右子樹
參考代碼例如以下：
void PreOrderTraverse(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return;Visit(pRoot); // 訪問根節點PreOrderTraverse(pRoot->m_pLeft); // 前序遍歷左子樹PreOrderTraverse(pRoot->m_pRight); // 前序遍歷右子樹
}（1）假設二叉樹為空，空操作。
（2）假設二叉樹不為空，中序遍歷左子樹，訪問根節點，中序遍歷右子樹
參考代碼例如以下：
void InOrderTraverse(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return;InOrderTraverse(pRoot->m_pLeft); // 中序遍歷左子樹Visit(pRoot); // 訪問根節點InOrderTraverse(pRoot->m_pRight); // 中序遍歷右子樹
}（1）假設二叉樹為空，空操作
（2）假設二叉樹不為空，后序遍歷左子樹，后序遍歷右子樹，訪問根節點
參考代碼例如以下：
void PostOrderTraverse(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return;PostOrderTraverse(pRoot->m_pLeft); // 后序遍歷左子樹PostOrderTraverse(pRoot->m_pRight); // 后序遍歷右子樹Visit(pRoot); // 訪問根節點
}4.分層遍歷二叉樹（按層次從上往下，從左往右）
相當于廣度優先搜索，使用隊列實現。隊列初始化，將根節點壓入隊列。當隊列不為空，進行例如以下操作：彈出一個節點，訪問，若左子節點或右子節點不為空，將其壓入隊列。
void LevelTraverse(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return;queue<BinaryTreeNode *> q;q.push(pRoot);while(!q.empty()){BinaryTreeNode * pNode = q.front();q.pop();Visit(pNode); // 訪問節點if(pNode->m_pLeft != NULL)q.push(pNode->m_pLeft);if(pNode->m_pRight != NULL)q.push(pNode->m_pRight);}return;
}遞歸解法：
（1）假設二叉樹查找樹為空，不須要轉換，相應雙向鏈表的第一個節點是NULL，最后一個節點是NULL
（2）假設二叉查找樹不為空：
假設左子樹為空，相應雙向有序鏈表的第一個節點是根節點，左邊不須要其它操作；
假設左子樹不為空，轉換左子樹，二叉查找樹相應雙向有序鏈表的第一個節點就是左子樹轉換后雙向有序鏈表的第一個節點，同一時候將根節點和左子樹轉換后的雙向有序鏈表的最后一個節點連接；
假設右子樹為空，相應雙向有序鏈表的最后一個節點是根節點，右邊不須要其它操作；
假設右子樹不為空，相應雙向有序鏈表的最后一個節點就是右子樹轉換后雙向有序鏈表的最后一個節點，同一時候將根節點和右子樹轉換后的雙向有序鏈表的第一個節點連接。參考代碼例如以下：
/******************************************************************************
參數：
pRoot: 二叉查找樹根節點指針
pFirstNode: 轉換后雙向有序鏈表的第一個節點指針
pLastNode: 轉換后雙向有序鏈表的最后一個節點指針
******************************************************************************/
void Convert(BinaryTreeNode * pRoot, BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)
{BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;if(pRoot == NULL) {pFirstNode = NULL;pLastNode = NULL;return;}if(pRoot->m_pLeft == NULL){// 假設左子樹為空，相應雙向有序鏈表的第一個節點是根節點pFirstNode = pRoot;}else{Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);// 二叉查找樹相應雙向有序鏈表的第一個節點就是左子樹轉換后雙向有序鏈表的第一個節點pFirstNode = pFirstLeft;// 將根節點和左子樹轉換后的雙向有序鏈表的最后一個節點連接pRoot->m_pLeft = pLastLeft;pLastLeft->m_pRight = pRoot;}if(pRoot->m_pRight == NULL){// 相應雙向有序鏈表的最后一個節點是根節點pLastNode = pRoot;}else{Convert(pRoot->m_pRight, pFirstRight, pLastRight);// 相應雙向有序鏈表的最后一個節點就是右子樹轉換后雙向有序鏈表的最后一個節點pLastNode = pLastRight;// 將根節點和右子樹轉換后的雙向有序鏈表的第一個節點連接pRoot->m_pRight = pFirstRight;pFirstRight->m_pLeft = pRoot;}return;
}遞歸解法：
（1）假設二叉樹為空或者k<1返回0
（2）假設二叉樹不為空而且k==1，返回1
（3）假設二叉樹不為空且k>1，返回左子樹中k-1層的節點個數與右子樹k-1層節點個數之和
參考代碼例如以下：
int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)
{if(pRoot == NULL || k < 1)return 0;if(k == 1)return 1;int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子樹中k-1層的節點個數int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子樹中k-1層的節點個數return (numLeft + numRight);
}遞歸解法：
（1）假設二叉樹為空，返回0
（2）假設二叉樹不為空且左右子樹為空，返回1
（3）假設二叉樹不為空，且左右子樹不同一時候為空，返回左子樹中葉子節點個數加上右子樹中葉子節點個數
參考代碼例如以下：
int GetLeafNodeNum(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return 0;if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)return 1;int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子樹中葉節點的個數int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子樹中葉節點的個數return (numLeft + numRight);
}不考慮數據內容。結構相允許味著相應的左子樹和相應的右子樹都結構同樣。
遞歸解法：
（1）假設兩棵二叉樹都為空，返回真
（2）假設兩棵二叉樹一棵為空，還有一棵不為空，返回假
（3）假設兩棵二叉樹都不為空，假設相應的左子樹和右子樹都同構返回真，其它返回假
參考代碼例如以下：
bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)
{if(pRoot1 == NULL && pRoot2 == NULL) // 都為空，返回真return true;else if(pRoot1 == NULL || pRoot2 == NULL) // 有一個為空，一個不為空，返回假return false;bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比較相應左子樹 bool resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比較相應右子樹return (resultLeft && resultRight);
} 遞歸解法：
（1）假設二叉樹為空，返回真
（2）假設二叉樹不為空，假設左子樹和右子樹都是AVL樹而且左子樹和右子樹高度相差不大于1，返回真，其它返回假
參考代碼：
bool IsAVL(BinaryTreeNode * pRoot, int & height)
{if(pRoot == NULL) // 空樹，返回真{height = 0;return true;}int heightLeft;bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);int heightRight;bool resultRight = IsAVL(pRoot->m_pRight, heightRight);if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子樹和右子樹都是AVL，而且高度相差不大于1，返回真{height = max(heightLeft, heightRight) + 1;return true;}else{height = max(heightLeft, heightRight) + 1;return false;}
}遞歸解法：
（1）假設二叉樹為空，返回空
（2）假設二叉樹不為空，求左子樹和右子樹的鏡像，然后交換左子樹和右子樹
參考代碼例如以下：
BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)
{if(pRoot == NULL) // 返回NULLreturn NULL;BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子樹鏡像BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子樹鏡像// 交換左子樹和右子樹pRoot->m_pLeft = pRight;pRoot->m_pRight = pLeft;return pRoot;
}遞歸解法：
（1）假設兩個節點分別在根節點的左子樹和右子樹，則返回根節點
（2）假設兩個節點都在左子樹，則遞歸處理左子樹；假設兩個節點都在右子樹，則遞歸處理右子樹
參考代碼例如以下：
bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)
{if(pRoot == NULL || pNode == NULL)return false;if(pRoot == pNode)return true;bool found = FindNode(pRoot->m_pLeft, pNode);if(!found)found = FindNode(pRoot->m_pRight, pNode);return found;
}BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)
{if(FindNode(pRoot->m_pLeft, pNode1)){if(FindNode(pRoot->m_pRight, pNode2))return pRoot;elsereturn GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);}else{if(FindNode(pRoot->m_pLeft, pNode2))return pRoot;elsereturn GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);}
}非遞歸解法：
先求從根節點到兩個節點的路徑，然后再比較相應路徑的節點即可，最后一個同樣的節點也就是他們在二叉樹中的最低公共祖先節點
參考代碼例如以下：
bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode, list<BinaryTreeNode *> & path)
{if(pRoot == pNode){ path.push_back(pRoot);return true;}if(pRoot == NULL)return false;path.push_back(pRoot);bool found = false;found = GetNodePath(pRoot->m_pLeft, pNode, path);if(!found)found = GetNodePath(pRoot->m_pRight, pNode, path);if(!found)path.pop_back();return found;
}
BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)
{if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)return NULL;list<BinaryTreeNode*> path1;bool bResult1 = GetNodePath(pRoot, pNode1, path1);list<BinaryTreeNode*> path2;bool bResult2 = GetNodePath(pRoot, pNode2, path2);if(!bResult1 || !bResult2) return NULL;BinaryTreeNode * pLast = NULL;list<BinaryTreeNode*>::const_iterator iter1 = path1.begin();list<BinaryTreeNode*>::const_iterator iter2 = path2.begin();while(iter1 != path1.end() && iter2 != path2.end()){if(*iter1 == *iter2)pLast = *iter1;elsebreak;iter1++;iter2++;}return pLast;
}在上述算法的基礎上稍加變化就可以求二叉樹中隨意兩個節點的距離了。
12. 求二叉樹中節點的最大距離
即二叉樹中相距最遠的兩個節點之間的距離。
遞歸解法：
（1）假設二叉樹為空，返回0，同一時候記錄左子樹和右子樹的深度，都為0
（2）假設二叉樹不為空，最大距離要么是左子樹中的最大距離，要么是右子樹中的最大距離，要么是左子樹節點中到根節點的最大距離+右子樹節點中到根節點的最大距離，同一時候記錄左子樹和右子樹節點中到根節點的最大距離。
參考代碼例如以下：
int GetMaxDistance(BinaryTreeNode * pRoot, int & maxLeft, int & maxRight)
{// maxLeft, 左子樹中的節點距離根節點的最遠距離// maxRight, 右子樹中的節點距離根節點的最遠距離if(pRoot == NULL){maxLeft = 0;maxRight = 0;return 0;}int maxLL, maxLR, maxRL, maxRR;int maxDistLeft, maxDistRight;if(pRoot->m_pLeft != NULL){maxDistLeft = GetMaxDistance(pRoot->m_pLeft, maxLL, maxLR);maxLeft = max(maxLL, maxLR) + 1;}else{maxDistLeft = 0;maxLeft = 0;}if(pRoot->m_pRight != NULL){maxDistRight = GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);maxRight = max(maxRL, maxRR) + 1;}else{maxDistRight = 0;maxRight = 0;}return max(max(maxDistLeft, maxDistRight), maxLeft+maxRight);
}二叉樹前序遍歷序列中，第一個元素總是樹的根節點的值。中序遍歷序列中，左子樹的節點的值位于根節點的值的左邊，右子樹的節點的值位
于根節點的值的右邊。
遞歸解法：
（1）假設前序遍歷為空或中序遍歷為空或節點個數小于等于0，返回NULL。
（2）創建根節點。前序遍歷的第一個數據就是根節點的數據，在中序遍歷中找到根節點的位置，可分別得知左子樹和右子樹的前序和中序遍
歷序列，重建左右子樹。
BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)return NULL;BinaryTreeNode * pRoot = new BinaryTreeNode;// 前序遍歷的第一個數據就是根節點數據pRoot->m_nValue = pPreOrder[0];pRoot->m_pLeft = NULL;pRoot->m_pRight = NULL;// 查找根節點在中序遍歷中的位置，中序遍歷中，根節點左邊為左子樹，右邊為右子樹int rootPositionInOrder = -1;for(int i = 0; i < nodeNum; i++)if(pInOrder[i] == pRoot->m_nValue){rootPositionInOrder = i;break;}if(rootPositionInOrder == -1){throw std::exception("Invalid input.");}// 重建左子樹int nodeNumLeft = rootPositionInOrder;int * pPreOrderLeft = pPreOrder + 1;int * pInOrderLeft = pInOrder;pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);// 重建右子樹int nodeNumRight = nodeNum - nodeNumLeft - 1;int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;int * pInOrderRight = pInOrder + nodeNumLeft + 1;pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);return pRoot;
}14.推斷二叉樹是不是全然二叉樹
若設二叉樹的深度為h，除第 h 層外，其他各層 (1～h-1) 的結點數都達到最大個數，第 h 層全部的結點都連續集中在最左邊，這就是全然
二叉樹。
有例如以下算法，按層次（從上到下，從左到右）遍歷二叉樹，當遇到一個節點的左子樹為空時，則該節點右子樹必須為空，且后面遍歷的節點左
右子樹都必須為空，否則不是全然二叉樹。
bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)
{if(pRoot == NULL)return false;queue<BinaryTreeNode *> q;q.push(pRoot);bool mustHaveNoChild = false;bool result = true;while(!q.empty()){BinaryTreeNode * pNode = q.front();q.pop();if(mustHaveNoChild) // 已經出現了有空子樹的節點了，后面出現的必須為葉節點（左右子樹都為空）{if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL){result = false;break;}}else{if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL){q.push(pNode->m_pLeft);q.push(pNode->m_pRight);}else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL){mustHaveNoChild = true;q.push(pNode->m_pLeft);}else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL){result = false;break;}else{mustHaveNoChild = true;}}}return result;
}
