二叉樹的面試題(一)

在本篇部落格中，通路節點，都是列印節點的數值，但是通路結點并不一定是列印數值，也可以是其他操作。

// 本着學習的心，有錯誤請指正。還有部分題沒有寫，改天寫

二叉樹的特點：(1) 每個結點的度都大于2。

(2) 每個結點的孩子結點次序不能任意颠倒，即有左右孩子之分。

二叉樹的性質：

(1)若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有 2^(i-1)個結點。

(2)若規定隻有根節點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是 (2^k)-1 。

(3)對任意一棵二叉樹T，若終端節點數為n0，而其度數為2的節點樹為n2,則n0 = n2+1 。

(4)具有n個結點的完全二叉樹的深度為 lgN+1。

性質經常要用到，最好能記住，

先給出二叉樹節點的定義：

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode(const T& data)
	:_data(data)
	, _pLeftChild(NULL)
	, _pRightChild(NULL)
	{}

	T _data;
	BinaryTreeNode<T>* _pLeftChild;
	BinaryTreeNode<T>* _pRightChild;
};

常見的題目：還有兩個題目求兩個節點的最低公共祖先和節點的最大距離

1 建立二叉樹

2 前序中序後序周遊（遞歸和非遞歸）

3層序周遊

4求二叉樹的深度

5求二叉樹中葉子結點的個數

6 求二叉樹中節點的個數

7求二叉樹第k層的節點個數

8判斷兩棵二叉樹是否結構相同

之後的面試題在下篇部落格：二叉樹面試題(二)

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

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

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

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

13 求二叉樹的鏡像

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

詳細解答

1建立二叉樹

思路：已前序周遊的特點來建立二叉樹，如果沒有左右孩子就用"#"來表示

注意：遞歸調用時_CreatBinaryTree()的參數pRoot 和index數組下标為引用，

BinaryTree(const T array[], size_t size)
		:_pRoot(NULL)
	{
		size_t index = 0;
		_CreatBinaryTree(_pRoot, array, size, index);
	}
	void _CreatBinaryTree(BinaryTreeNode<T>*& pRoot,const T array[], size_t size, size_t& index) 
	{ 
		if (index < size && '#' != array[index])
		{
			pRoot = new BinaryTreeNode<T>(array[index]);
			_CreatBinaryTree(pRoot->_pLeftChild,array,size,++index);
			_CreatBinaryTree(pRoot->_pRightChild,array,size,++index);
		}
	}

2 前序，中序，後序周遊(遞歸和非遞歸) //

(1)前序遞歸周遊：先通路根節點，再通路左右子樹

void _PreOreder(BinaryTreeNode<T>* proot) //前序周遊
	{
		if (proot)
		{
			cout << proot->_data << " ";
			_PreOreder(proot->_pLeftChild);
			_PreOreder(proot->_pRightChild);
		}
	}

前序非遞歸周遊：基于棧的遞歸消除，實作周遊，棧是後進先出，先存放右孩子在存放左孩子

思路： 1從根節點出發，根節點不為空時入棧，隻有棧不為空循環進行下面操作

2通路目前棧頂，出棧，右孩子存放入棧，左孩子存在入棧

void PreOrder_Nor() //非遞歸
	//在棧中存放（後進先出） 先存放右孩子，再存放左孩子
	{
		cout << "前序周遊" << endl;
		if (_pRoot == NULL)
			return;
		stack<BinaryTreeNode<T>*> s;
		s.push(_pRoot);
		while (!s.empty())
		{
			BinaryTreeNode<T>* pCur = s.top();
			cout << pCur->_data << " "; //通路目前節點
			s.pop(); 
			if (pCur->_pRightChild)
				s.push(pCur->_pRightChild);
			if (pCur->_pLeftChild)
				s.push(pCur->_pLeftChild);
		}
	}

(2)中序遞歸周遊：先通路左孩子，再通路根節點，然後通路右孩子

void _InOrder(BinaryTreeNode<T>* proot) //中序周遊
	{
		if (proot)
		{			
			_InOrder(proot->_pLeftChild);
			cout << proot->_data << " "; //通路根節點
			_InOrder(proot->_pRightChild);
		}
	}

中序非遞歸周遊：從根節點開始，隻有目前節點存在或者棧不為空，則重複下面的工作

1如果目前結點存在，則進棧并周遊左子樹

2否則退棧并通路，然後周遊右子樹

void InOrder_Nor() //非遞歸
	{
		cout << "中序周遊" << endl;
		if (NULL == _pRoot)
			return;


		BinaryTreeNode<T>* pCur = _pRoot;
		stack<BinaryTreeNode<T>*> s;
		while (NULL != pCur || !s.empty())
		{
			while (pCur) //存放節點，找到最左邊的節點
			{
				s.push(pCur);
				pCur = pCur->_pLeftChild;
			}
			
			
			BinaryTreeNode<T>* pTop = s.top();
			cout << pTop->_data << " ";
			pCur = pTop->_pRightChild; //再找目前節點的右子樹的最左邊
			s.pop();
					
		}
		cout << endl;
	}

(3)後序遞歸周遊：先通路左子樹，再通路右子樹，最後通路根節點

void _PostOrder(BinaryTreeNode<T>* proot)  //後續周遊
	{
		if (proot)
		{
			_PostOrder(proot->_pLeftChild);
			_PostOrder(proot->_pRightChild);
			cout << proot->_data << " "; 
		}
	}

後序非遞歸周遊：由于後序周遊是LRD，要求左右子樹都通路完後，最後通路根節點。

判别是否應該通路目前棧頂節點p時，有兩種情況：①p無右孩子，②p的右孩子是剛被通路過的節點。

除這兩種情況外，均不能通路根，而是繼續進入右子樹中。

思路：①從目前節點開始，進棧并周遊左子樹，直到左子樹為空。

②如果棧頂節點的右子樹為空或者棧頂節點的右孩子剛被通路過的結點，則退棧并通路，

③否則周遊右子樹

void PostOrder_Nor() //非遞歸
	// 存放到棧中：先找到樹的最左邊，
	{
		cout << "後序周遊" << endl;
		if (NULL == _pRoot)
			return;
		BinaryTreeNode<T> *pCur = _pRoot;
		BinaryTreeNode<T>* pPre = NULL; //儲存已通路過的右子樹
		stack<BinaryTreeNode<T>*> s;
		while (NULL != pCur || !s.empty())
		{
			while (pCur) //周遊左子樹
			{
				s.push(pCur);
				pCur = pCur->_pLeftChild;
			}
			BinaryTreeNode<T>* pTop = s.top();
			if (NULL == pTop->_pRightChild || pTop->_pRightChild == pPre) //判斷右子樹是否為空或者通路過
			{
				cout << pTop->_data << " ";
				pPre = pTop;//儲存已通路過的結點
				s.pop();
			}
			else
			{
				pCur = pTop->_pRightChild;
			}
		}
	}

3層序周遊二叉樹：存放在隊列中(先進先出) 先存放根節點，再存放左孩子，再存放右孩子

void LevelOrder() //層序周遊
		//存放在隊列中：先存放根節點，再存放左孩子，再存放右孩子
	{
		cout << "層次周遊" << endl;
		if (NULL == _pRoot)
			return;
		queue<BinaryTreeNode<T> *> q;
		if (_pRoot)
			q.push(_pRoot);
		while (!q.empty())
		{
			BinaryTreeNode<T>* pCur = q.front();
			cout << pCur->_data << " ";
			q.pop();	
			if (pCur->_pLeftChild)
				q.push(pCur->_pLeftChild);
			if (pCur->_pRightChild)
				q.push(pCur->_pRightChild);
		}	
	}

4求二叉樹的深度：

思路：①若bt為空，則高度為0

②若bt為空，則高度為左右子樹高度的最大值加1.

size_t _Height(BinaryTreeNode<T>* pRoot)
	{
		if (NULL == pRoot)
			return 0;
		if (NULL == pRoot->_pLeftChild && NULL == pRoot->_pRightChild)
			return 1;
		size_t LHeigt = _Height(pRoot->_pLeftChild);
		size_t RHeight = _Height(pRoot->_pRightChild);
		return (LHeigt > RHeight) ? (LHeigt + 1) : (RHeight + 1);
	}

5求二叉樹中葉子結點的個數

有兩種思路：采用周遊算法，隻需将通路操作變為判斷是否為葉子結點以及統計即可，

采用遞歸算法，如果空樹傳回0，如果隻有一個節點(根節點)傳回1，否則為左右子樹的葉子結點樹之和

①後序周遊統計葉子結點個數

//注意LeafCount為儲存葉子結點的全局變量，調用前初始化為0；

void _GetLeafNodeNum2(BinaryTreeNode<T>* pRoot)
		//後序周遊統計葉子結點
	{
		if (pRoot != NULL)
		{
			_GetLeafNodeNum2(pRoot->_pLeftChild);
			_GetLeafNodeNum2(pRoot->_pRightChild);
			if (pRoot->_pLeftChild == NULL && pRoot->_pRightChild == NULL)
				leftCountt++;
		}
	}

②//遞歸調用

size_t _GetLeafNodeNum(BinaryTreeNode<T>* pRoot)
	// 采用遞歸算法，如果空樹傳回0，如果隻有一個節點(根節點)傳回1，否則為左右子樹的葉子結點樹之和
	{
		size_t leafCount = 0;
		if (pRoot == NULL)
			leafCount = 0;
		else if (pRoot->_pLeftChild == NULL && pRoot->_pRightChild == NULL)
			leafCount = 1;
		else
			leafCount = _GetLeafNodeNum(pRoot->_pLeftChild) + _GetLeafNodeNum(pRoot->_pRightChild);
		return leafCount;
	}

6求二叉樹中節點的個數

遞歸解法：

（1）如果二叉樹為空，節點個數為0

（2）如果二叉樹不為空，二叉樹節點個數 = 左子樹節點個數 + 右子樹節點個數 + 1

size_t _GetNodeNum(BinaryTreeNode<T>* pRoot)
	{
		if (pRoot == NULL)
			return 0;
		else
			return _GetNodeNum(pRoot->_pLeftChild) + _GetNodeNum(pRoot->_pRightChild) + 1;
	}

7求二叉樹中第K層的節點個數

遞歸解法：

（1）如果二叉樹為空或者k<1傳回0

（2）如果二叉樹不為空并且k==1，傳回1

（3）如果二叉樹不為空且k>1，傳回左子樹中k-1層的節點個數與右子樹k-1層節點個數之和

size_t _GetKthLeverNodeNum(BinaryTreeNode<T>* pRoot,size_t k)
	{
		if (pRoot == NULL || k == 0)
			return 0;
		if (k == 1 && pRoot != NULL)
			return 1;
		int leftNum = _GetKthLeverNodeNum(pRoot->_pLeftChild,k-1);
		int rightNum = _GetKthLeverNodeNum(pRoot->_pRightChild,k-1);
		return leftNum + rightNum;
	}

8判斷兩棵二叉樹是否結構相同

不考慮資料内容。結構相同意味着對應的左子樹和對應的右子樹都結構相同。

遞歸解法：

（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);
	}

其他面試題在下篇部落格：二叉樹面試題(二)

二叉樹的面試題(一)

繼續閱讀

JAVA高效程式設計指南

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

雲計算面試題——mysql/存儲引擎/備份

雲計算面試題——檔案/權限/分區/軟體包管理

[轉]ISUP信令的IAM消息詳細内容

測試理論面試題

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

面試題解析：你接口測試是怎麼做的？

測試面試題整理

軟體測試經典面試題（小題彙總）

Linux裝置模型（中）之上層容器