天天看點
傳回

二叉樹的面試題(二)

接着上篇部落格接着講述二叉樹的面試題 ：二叉樹面試題(一)

9 由前序周遊序列和中序周遊序列重建二叉樹

10 判斷一個節點是否在二叉樹中

11 判斷二叉樹是不是平衡二叉樹

12 判斷一顆二叉樹是否為完全二叉樹

13 求二叉樹的鏡像

14 将二叉查找樹變為有序的雙向連結清單

9 由前序周遊序列和中序周遊序列重建二叉樹

 周遊組合唯一 确定二叉樹：必須包含中序周遊才能唯一确定二叉樹

思路：二叉樹前序周遊序列中，第一個元素總是樹的根節點的值。中序周遊序列中，左子樹的節點的值位于根節點的值的左邊，右子樹的節點的值位于根節點的右邊。

遞歸解法：

（1）如果前序周遊為空或中序周遊為空或節點個數小于等于0，傳回NULL。

（2）建立根節點。前序周遊的第一個資料就是根節點的資料，在中序周遊中找到根節點的位置，可分别得知左子樹和右子樹的前序和中序周遊序列，重建左右子樹。

BinaryTreeNode<T>* _ConstructTree(T *startPreOrder,T *endPreOrder,T *startInOrder,T *endInOrder)
	{
		//前序周遊的第一個結點為根節點
		T rootValue = startPreOrder[0];
		BinaryTreeNode<T>* pRoot = new	BinaryTreeNode<T>(rootValue);
		//隻有一個元素
		if (startPreOrder == endPreOrder && *startInOrder == *startPreOrder)
			return pRoot;
		//在中序周遊中找到根節點的值
		T* rootInOreder = startInOrder;
		while (rootInOreder <= endInOrder && *rootInOreder != rootValue)
		{
			++rootInOreder;
		}//跳出循環可能沒有找到
		if (*rootInOreder != rootValue)
			throw std::exception("Invalid input");

		int leftlength = rootInOreder - startInOrder; //左子樹的長度
		T *leftPreEnd = startPreOrder + leftlength; //前序左子樹的end位置
		if (leftlength > 0)//建構左子樹
		{
			pRoot->_pLeftChild = _ConstructTree(startPreOrder + 1, leftPreEnd, startInOrder, rootInOreder - 1);
		}
		if (leftlength < endPreOrder - startPreOrder)//建構右子樹
		{
			pRoot->_pRightChild = _ConstructTree(leftPreEnd + 1, endPreOrder, rootInOreder + 1, endInOrder);
		}
		return pRoot;
	}

10 判斷一個節點是否在二叉樹中

思路：先看該節點是否在為根節點，在檢視左子樹，再檢視右子樹

BinaryTreeNode<T>* _Find(BinaryTreeNode<T>* pRoot, const T& data)
	{
		if (pRoot == NULL)
			return NULL;
		if (pRoot->_data == data)
			return pRoot;
		BinaryTreeNode<T>* find;
		if (find = _Find(pRoot->_pLeftChild, data))
			return find;
		return _Find(pRoot->_pRightChild, data);
	}

11 判斷二叉樹是不是平衡二叉樹

遞歸解法：

(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;  
    }  
}

12 判斷一顆二叉樹是否為完全二叉樹

思路：判斷二叉樹是否為完全二叉樹。完全二叉樹的定義是，前n-1層都是滿的，第n層如有空缺，則是缺在右邊，即第n層的最右邊的節點，它的左邊是滿的，右邊是空的。

解法：采用廣度優先周遊，從根節點開始，入隊列，如果隊列不為空，循環。遇到第一個沒有左兒子或者右兒子的節點，設定标志位，如果之後再遇到有左/右兒子的節點，那麼這不是一顆完全二叉樹。

bool IsCompleteBinaryTree(BinaryTreeNode<T> *pRoot )
	{
		//空樹也是完全二叉樹
		if (pRoot == NULL)
			return true; 
		queue<BinaryTreeNode<T>*> q;
		q.push(pRoot); //根節點入隊
		bool mustLeft = false;
		bool result = true;
		while (!q.empty())
		{
			BinaryTreeNode<T> *pCur = q.front();
			q.pop();
			if (mustLeft) //出現了 空子樹的節點
			{
				if (pCur->_pLeftChild != NULL || pCur->_pRightChild != NULL)
				{
					result = false;
					break;
				}
			}
			else 
			{
				if (pCur->_pLeftChild != NULL && pCur->_pRightChild != NULL)
				{
					q.push(pCur->_pLeftChild);
					q.push(pCur->_pRightChild);
				}
				else if (pCur->_pLeftChild == NULL && pCur->_pRightChild != NULL)
				{
					result = false;
					break;
				}
				else if (pCur->_pRightChild == NULL && pCur->_pLeftChild != NULL)
				{
					q.push(pCur->_pLeftChild);
					mustLeft = true;
				}
				else
				{
					mustLeft = true;
				}
			}
		}
		return result;
	}

另一種思路：

任意的一個二叉樹，都可以補成一個滿二叉樹。這樣中間就會有很多空洞。在廣度優先周遊的時候，如果是滿二叉樹，或者完全二叉樹，這些空洞是在廣度優先的周遊的末尾，是以，但我們周遊到空洞的時候，整個二叉樹就已經周遊完成了。而如果，是非完全二叉樹，我們周遊到空洞的時候，就會發現，空洞後面還有沒有周遊到的值。這樣，隻要根據是否周遊到空洞，整個樹的周遊是否結束來判斷是否是完全的二叉樹。

bool IsCompleteTree(BinaryTreeNode<T> *pRoot)
	{
		if (pRoot == NULL)
			return true;
		queue<BinaryTreeNode<T>*> q;
		q.push(pRoot);
		BinaryTreeNode<T>* pCur = NULL;
		//層序周遊二叉樹 ,當遇到空節點是退出
		while ((pCur = q.front()) != NULL)
		{
			q.pop();
			q.push(pCur->_pLeftChild);
			q.push(pCur->_pRightChild);
		}
		q.pop();//把目前節點為空出隊
		//檢視剩餘隊列中是否有不為空的節點
		while (!q.empty())
		{
			if (q.front() != NULL)
				return false;
			q.pop();
		}
		return true;
	}

13 求二叉樹的鏡像

遞歸解法：

（1）如果二叉樹為空，傳回空

（2）如果二叉樹不為空，求左子樹和右子樹的鏡像，然後交換左子樹和右子樹

BinaryTreeNode<T>* Mirror(BinaryTreeNode<T> * pRoot)
	{
		if (pRoot == NULL) // 傳回NULL  
			return NULL;
		BinaryTreeNode<T> * pLeft = Mirror(pRoot->_pLeftChild); // 求左子樹鏡像  
		BinaryTreeNode<T> * pRight = Mirror(pRoot->_pRightChild); // 求右子樹鏡像  
		// 交換左子樹和右子樹  
		pRoot->_pLeftChild = pRight;
		pRoot->_pRightChild = pLeft;
		return pRoot;
	}

14将二叉查找樹變為有序的雙向連結清單

要求：不能建立新的節點，隻能調整樹種節點指針的指向

在二叉搜尋樹中，每個結點都有兩個分别指向其左、右子樹的指針，左子樹結點的值總是小于父結點的值，右子樹結點的值總是大于父結點的值。

思路：(1)由于要求連結清單是有序的，可以借助二叉樹中序周遊，因為中序周遊算法的特點就是從小到大通路結點。當周遊通路到根結點時，假設根結點的左側已經處理好，隻需将根結點與上次通路的最近結點（左子樹中最大值結點）的指針連接配接好即可。進而更新目前連結清單的最後一個結點指針。

(2)由于中序周遊過程正好是轉換成連結清單的過程，即可采用遞歸處理

void ConvertNode(BinaryTreeNode<T>* pNode, BinaryTreeNode<T>** pLastNodeInList)
	{
		if (pNode == NULL)
			return;
		BinaryTreeNode<T>* pCurrent = pNode;
		//遞歸處理左子樹  
		if (pCurrent->_pLeftChild != NULL)
			ConvertNode(pNode->_pLeftChild, pLastNodeInList);
		//處理目前結點              
		pCurrent->_pLeftChild = *pLastNodeInList;    //将目前結點的左指針指向已經轉換好的連結清單的最後一個位置  
		if (*pLastNodeInList != NULL)
			(*pLastNodeInList)->_pRightChild = pCurrent;//将已轉換好的連結清單的最後一個結點的右指針指向目前結點  

		*pLastNodeInList = pCurrent;//更新連結清單的最後一個結點  
		//遞歸處理目前結點的右子樹  
		if (pCurrent->_pRightChild != NULL)
			ConvertNode(pNode->_pRightChild, pLastNodeInList);
	}
BinaryTreeNode<T>* Convert(BinaryTreeNode<T>* pRootInTree)
	{
		BinaryTreeNode<T>* pLastNodeInList = NULL;

		ConvertNode(pRootInTree, &pLastNodeInList);

		//pLastNodeInList指向雙向連結清單的尾結點，再次周遊找到頭結點  
		BinaryTreeNode<T>* pHeadOfList = pLastNodeInList;
		while (pHeadOfList != NULL && pHeadOfList->_pLeftChild != NULL)
			pHeadOfList = pHeadOfList->_pLeftChild;

		return pHeadOfList;
	}
資料結構 樹 二叉樹 面試題
上一篇: [No.003-6]爬蟲網易賠率資料并導入到mysql資料庫
下一篇: 伺服器型号變更說明,伺服器變更規格通用操作

繼續閱讀