若干數據結構 && 算法面試題【四】（更新ing)

這是我的第三個面試題匯總。

想看之前的內容請移步

http://zhweizhi.blog.51cto.com/10800691/1763237

 若干數據結構 && 算法面試題【一】更新完畢

http://zhweizhi.blog.51cto.com/10800691/1775780

 若干數據結構 && 算法面試題【二】更新完畢

http://zhweizhi.blog.51cto.com/10800691/1787562

 若干數據結構 && 算法面試題【三】更新完畢

另外我的全部刷題代碼都在這里

https://github.com/HonestFox/BrushQuestion

//第四篇啦終于放暑假啦可以安安心心學習啦  (●ˇˇ●)

//因為剛開始刷題的時候還沒有接觸過二叉樹，所以只要遇到二叉樹的問題就跳過了

//慢慢的居然積壓了這么多，

//如今題總算快刷完了  接下來的這些問題主要是 二叉樹相關的面試題了

————————————————————————————————————————

一、帶環鏈表中環的入口

題目描述:
一個鏈表中包含環請找出該鏈表的環的入口結點。

分析

    · 首先用兩個指針 Fast 和 SlowFast每次走兩步Slow每次走一步這樣最終這兩個指針會在環內相遇相遇時讓它們停下來;

    · 這時設Slow走的步數為s則Fast走的步數為2s 此外Fast肯定比Slow多走一個環長 r所以 s = r

    · 設起點到環入口點這一段的長度為x    則相遇時Slow在環內走了 r - x,  那么相遇點繼續走也就是后半部分到環入口的距離為   r - (r - x) = x   可以看出x剛好也是起點到環入口的舉例

    · 所以再讓兩個指針分別從pHead 和 相遇點開始每次走一步直到兩個指針相交這時的交點就是環的入口

    ·

代碼

 ListNode* EntryNodeOfLoop(ListNode* pHead)
 {
  if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL)
  {
   return NULL;
  }
  if (pHead->next == pHead)
  {
   return pHead;
  }
  ListNode *FastNode = pHead;
  ListNode *SlowNode = pHead;
  while (FastNode != SlowNode || FastNode == pHead)
  {
   FastNode = FastNode->next->next;
   SlowNode = SlowNode->next;
   if (SlowNode == pHead)
   {
    return pHead;;
   }
  }
  ListNode *pos = FastNode;
  ListNode *cur = pHead;
  while (FastNode != cur)
  {
   FastNode = FastNode->next;
   cur = cur->next;
  }
  return cur;
 }

github:

https://github.com/HonestFox/BrushQuestion/blob/master/55_%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3%E7%BB%93%E7%82%B9

二、二叉樹的下一個結點

題目描述:
給定一個二叉樹和其中的一個結點請找出中序遍歷順序的下一個結點并且返回。
注意樹中的結點不僅包含左右子結點同時包含指向父結點的指針。

github:

https://github.com/HonestFox/BrushQuestion/blob/master/56_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E8%8A%82%E7%82%B9

三、對稱的二叉樹

題目描述
請實現一個函數用來判斷一顆二叉樹是不是對稱的。注意如果一個二叉樹同此二叉樹的鏡像是同樣的定義其為對稱的。

github

https://github.com/HonestFox/BrushQuestion/blob/master/57_%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91

四、把二叉樹打印成多行

題目描述
從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

github：

https://github.com/HonestFox/BrushQuestion/blob/master/58_%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%A0%91%E6%89%93%E5%8D%B0%E6%88%90%E5%A4%9A%E8%A1%8C

五、之字形打印二叉樹

題目描述

請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

github：

https://github.com/HonestFox/BrushQuestion/blob/master/59_%E4%B9%8B%E5%AD%97%E5%BD%A2%E6%89%93%E5%8D%B0%E4%BA%8C%E5%8F%89%E6%A0%91

六、序列化與反序列化二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/60_%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91

七、求二叉樹中兩個節點最近的公共祖先結點

struct TreeNode
{
public:
	TreeNode(int val)
		:_val(val)
		, _left(NULL)
		, _right(NULL)
	{}
public:
	int _val;
	TreeNode *_left;
	TreeNode *_right;
};

可以訪問父節點的話：

  首先，假設如果這顆二叉樹的結點可以有指向父節點的指針，那么問題可以轉化為對一顆三叉鏈，給定兩個結點求他們最近的公共祖先結點。

   所以，如果對上圖這顆樹的 5結點 和 8結點求他們的公共祖先結點，我們可以獲得他們到根節點的鏈表形式路徑，并且這兩個鏈表肯定是相交的。它們分別是：   8 -> 4 -> 2 -> 1    以及   5 -> 2 -> 1   

     這樣，問題就轉化成：尋找兩個鏈表的第一處交點。

時間復雜度O(log2(N) * 5)   =  O(log2(N)

如果這棵樹是搜索樹的話：

   我們知道，對于一顆二叉搜索樹的每個結點都滿足：左子樹的所有結點的值都小于當前結點，右子樹的所有節點的值都大于當前結點。 

   因此，如果給定兩個結點，就可以從根節點開始，判斷當前結點的值和兩個目標節點的值的大小關系：

 1、如果當前結點的值比其中一個要找的結點小，比另一個要找的結點大，則說明要找的兩個結點分別在這個結點的左右子樹中，所以當前結點一定是要找的結點。

 2、如果當前結點比要找的兩個結點都大，則說明兩個結點都在當前結點的左子樹，那么就在左子樹里面繼續找。

 3、如果當前結點比要找的兩個結點都小，反之。

現在將這棵樹限制為一顆普通的二叉樹：

   這時，就沒法再利用數值上的關系來確定結點在當前結點的左樹中還是右樹中了...不過，還是可以用這種思路，只不過在確定目標節點的位置時，需要遍歷來找。

    代碼中，我用的實際上時前序遍歷，對每一個結點 都可以看成一個單獨的問題，先判斷當前結點的左結點和右結點有沒有要找的結點，如果有，直接返回當前結點，如果沒有，就在其左子樹和右子樹里繼續找，如果左子樹和右子樹都找到了，則說明當前結點就是要找的結點；如果只有其中一側找到了，則將找到的那一側的子樹視為一個新的子問題。（都沒找到？）

 具體的代碼實現如下：

class BinaryTree()
{
public:
    TreeNode* GetNearRoot_2(TreeNode *Node1, TreeNode *Node2)
	{
		return _GetNearRoot_2(_root, Node1, Node2);
	}
protected:
	TreeNode* _GetNearRoot_2(TreeNode *root, TreeNode *Node1, TreeNode *Node2)
	{
		if (root == NULL || Node1 == NULL || Node2 == NULL)
		{
			return NULL;
		}
		if (root->_left == Node1 || root->_right == Node1 || root->_left == Node2 || root->_right == Node2)
		{
			return root;
		}
		TreeNode *pLeft = _GetNearRoot_2(root->_left, Node1, Node2);
		TreeNode *pRight = _GetNearRoot_2(root->_right, Node1, Node2);


		if (pLeft != NULL && pRight != NULL)	//左右都不為空，說明分別在根節點的 左右 子樹 ，則肯定他們的最近父節點就是根節點
		{
			return root;
		}
		else if (pLeft != NULL)
		{
			return pLeft;
		}
		else if (pRight != NULL)
		{
			return pRight;
		}
	}
protected:
    TreeNode *_root;

}

    其實可以看出，我用遞歸實現需要注意的就是，找到了以后，要將當前結點傳遞回上層的遞歸，這里我用返回值的方式向上傳遞。

（舉例子說明 --2）

    采用這種方法，思路比較簡單，代碼坑比較多。

    時間復雜度為 O(N) * O(N)

比較高效的方法：

    其實，可以觀察到，從根節點到目標結點，都有一條唯一的路徑。因此從根節點到我們要找的兩個結點，就有兩條路徑，并且這兩條路徑的起點肯定相同（都是根結點），那么我們可以在這兩條路徑中找出它們分開的結點，也就是我們要找的結點了。

代碼：

class BinaryTree
{
public:
	typedef vector<vector <TreeNode*> > PathVec;

	TreeNode* GetNearRoot_3(TreeNode *Node1, TreeNode *Node2)
	{
		//獲取兩條路徑
		PathVec path;
		path.resize(2);
		path[0] = _GetPath(Node1);
		path[1] = _GetPath(Node2);
		//找開始不同的結點的前一個結點
		TreeNode *DifferentNode = _GetDivide(path);
		return DifferentNode;
	}
protected:
	//獲得從根節點到Node的路徑
	vector<TreeNode*> _GetPath(TreeNode *Node)
	{
		vector<TreeNode*> ret;
		_PrevOrder(_root, Node, ret);
		return ret;
	}
	void _PrevOrder(TreeNode *root, TreeNode *Node, vector<TreeNode*> &ret)
	{
		if (root == NULL)
		{
			return;
		}
		ret.push_back(root);
		if (root == Node)
		{
			return;
		}
		else if (root->_left == NULL && root->_right == NULL)
		{
			ret.pop_back();
			return;
		}
		_PrevOrder(root->_left, Node, ret);
		if (*(ret.end() - 1) == Node)
		{
			return;
		}
		_PrevOrder(root->_right, Node, ret);
		if (*(ret.end() - 1) == Node)
		{
			return;
		}
		ret.pop_back();
	}
	//從路徑中找出分離點
	TreeNode* _GetDivide(PathVec path)
	{
		int i = 0;
		while (i < path[0].size() && i < path[1].size() && (path[0])[i] == (path[1])[i])
		{
			++i;
		}
		if (i > 0 && i == path[0].size() || i == path[1].size()) //如果兩個結點在同一顆子樹，會出現這種情況
		{
			--i;
		}
		return path[0][i - 1];
	}
protected:
	TreeNode *_root;
};

兩條路徑，并且這兩條路徑的起點肯定相同（都是根結點），那么我們可以在這兩條路徑中找出它們分開的結點，也就是我們要找的結點了。

    時間復雜度： O(N * 2 + log2(N) * 2) = O(N)

    空間復雜度： O(log2(N) * 2) = O(log2(N))

github：

https://github.com/HonestFox/BrushQuestion/blob/master/61_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E6%9C%80%E8%BF%91%E7%9A%84%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88%E8%8A%82%E7%82%B9

八、判斷一顆二叉樹是否為平衡二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/62_%E5%88%A4%E6%96%AD%E4%B8%80%E9%A2%97%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91

九、求二叉樹中最遠兩個節點的距離 

github：

https://github.com/HonestFox/BrushQuestion/blob/master/63_%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E6%9C%80%E8%BF%9C%E4%B8%A4%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E8%B7%9D%E7%A6%BB

十、由前序遍歷和中序遍歷重建二叉樹

github：

https://github.com/HonestFox/BrushQuestion/blob/master/64_%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%88STL%EF%BC%89

十一、二叉搜索樹的第k個節點

github：

https://github.com/HonestFox/BrushQuestion/blob/master/65_%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E7%AC%ACK%E4%B8%AA%E7%BB%93%E7%82%B9

十二、判斷一個序列是否為二叉樹的后序遍歷序列

github：

https://github.com/HonestFox/BrushQuestion/blob/master/66_%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97

十三、數據流中的中位數

（8.30恢復更新 ）

（開學了  /(ㄒoㄒ)/~~）

題目描述：

如何得到一個數據流中的中位數？

如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。

如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。

分析：

思路1：討論區都在用堆做，但其實用哈希的思想也可以做的，只要考慮清楚如下兩點：

1、重復的數字怎么處理

2、絕對值相等但符號相反的數字怎么處理

代碼如下，

#include <iostream>
#include <vector>

using namespace std;

/*
題目描述：
如何得到一個數據流中的中位數？
如果從數據流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值。
如果從數據流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值。
*/


struct Pos
{
	int _count = 0;				 //記錄該位置下標對應數據出現的次數  （為什么要這個變量？因為有可能有重復的數據）
	bool _IsExist = false;	 //記錄是否存在
};

class Solution
{
public:
	void Insert(int num)
	{
		if (num < 0)
		{
			num *= -1;
			_Insert(_Nvec, num, -1);
			++_NSize;
		}
		else
		{
			_Insert(_Pvec, num, 1);
			++_PSize;
		}
	}

	double GetMedian()
	{
		int size = _PSize + _NSize;
		int pos = _PSize - _NSize;      //size   pos  奇偶性一定是相同的
		int symbol = 1;
		if (pos < 0)
		{
			symbol = -1;
			pos *= -1;
		}
		double ret = 0;
		if (pos % 2 == 0)		//偶數
		{
			if (symbol == 1)
			{
				ret = ((double)_GetIndexVal(_Pvec, pos / 2) + (double)_GetIndexVal(_Pvec, pos / 2 - 1)) / 2;
			}
			else
			{
				ret = ((double)_GetIndexVal(_Nvec, pos / 2) + (double)_GetIndexVal(_Nvec, pos / 2 - 1) ) / 2;
			}
		}
		else						//奇數
		{
			if (symbol == 1)
			{
				ret = _GetIndexVal(_Pvec, pos / 2);
			}
			else
			{
				ret = _GetIndexVal(_Nvec, pos / 2);
			}
		}
		ret *= symbol;
		return ret;
	}

protected:
	void _Insert(vector<Pos> &vec, int num, int symbol = 1)
	{
		//判斷容量
		if (num >= vec.size())
		{
			vec.resize(num * 2 + 1);
		}
		//生成結點
		Pos pos;
		pos._IsExist = true;
		++pos._count;
		//插入
		vec[num] = pos;
	}

	int _GetIndexVal( vector<Pos> vec, int pos)           //pos表示第幾個元素 
	{
		int index = 0;
		while (pos >= 0)
		{
			while (pos >= 0 && vec[index]._IsExist && vec[index]._count > 0)
			{
				--vec[index]._count;
				--pos;
				if (vec[index]._count == 0)
				{
					vec[index]._IsExist = false;
				}
			}
			if (pos < 0)
			{
				break;
			}
			++index;
		}
		return index;
	}

protected:
	vector<Pos> _Pvec;		//存放正數的數組
	vector<Pos> _Nvec;		//存放負數的數組
	int _PSize = 0;						//正數的數目
	int _NSize = 0;						//負數的數目
};

int main()
{
	Solution s;
	s.Insert(-1);
	s.Insert(-2);
	s.Insert(-3);
	s.Insert(-4);
	s.Insert(1);
	s.Insert(2);
	double ret = s.GetMedian();
	cout << ret << endl;
	return 0;

}

github： https://github.com/HonestFox/BrushQuestion/blob/master/67_%E6%95%B0%E6%8D%AE%E6%B5%81%E4%B8%AD%E7%9A%84%E4%B8%AD%E4%BD%8D%E6%95%B0

(9.3恢復更新)

十四、將功贖罪

github：

https://github.com/HonestFox/BrushQuestion/blob/master/68_%E5%B0%86%E5%8A%9F%E8%B5%8E%E7%BD%AA

十五、矩陣中的路徑

github：

https://github.com/HonestFox/BrushQuestion/blob/master/69_%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84