作者簡介：大家好，我是未央；

博客首頁：未央.303

系列專欄：牛客面試必刷TOP101

每日一句：人的一生，可以有所作為的時機只有一次，那就是現(xiàn)在！！！！！

文章目錄

前言

一、二叉搜索樹的最近公共祖先

題目描述

解題分析

二、用兩個棧實現(xiàn)隊列

題目描述

解題分析

總結(jié)

---

前言

一、二叉搜索樹的最近公共祖先

題目描述

描述：

給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

1.對于該題的最近的公共祖先定義:對于有根樹T的兩個節(jié)點p、q，最近公共祖先LCA(T,p,q)表示一個節(jié)點x，滿足x是p和q的祖先且x的深度盡可能大。在這里，一個節(jié)點也可以是它自己的祖先.

2.二叉搜索樹是若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值； 若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值

3.所有節(jié)點的值都是唯一的。

4.p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。

---

數(shù)據(jù)范圍:

3<=節(jié)點總數(shù)<=10000

0<=節(jié)點值<=10000

---

舉例說明：

如果給定以下搜索二叉樹: {7,1,12,0,4,11,14,#,#,3,5}，如下圖:

---

示例1：

---

示例2：

解題分析

解題思路：
二叉搜索樹的定義：

二叉搜索樹是一種特殊的二叉樹，它的每個節(jié)點值大于它的左子節(jié)點，且大于全部左子樹的節(jié)點值，小于它右子節(jié)點，且小于全部右子樹的節(jié)點值。因此二叉搜索樹一定程度上算是一種排序結(jié)構(gòu)。

圖示舉例說明：

---

思路：

二叉搜索樹沒有相同值的節(jié)點，因此分別從根節(jié)點往下利用二叉搜索樹較大的數(shù)在右子樹，較小的數(shù)在左子樹，可以輕松找到p、q；

//節(jié)點值都不同，可以直接用值比較
while(node.val != target) { path.add(node.val);//小的在左子樹if(target < node.val) node = node.left;//大的在右子樹else node = node.right;
}

直接得到從根節(jié)點到兩個目標節(jié)點的路徑，這樣我們利用路徑比較就可以找到最近公共祖先。

---

解題步驟：

• step 1：根據(jù)二叉搜索樹的性質(zhì)，從根節(jié)點開始查找目標節(jié)點，當前節(jié)點比目標小則進入右子樹，當前節(jié)點比目標大則進入左子樹，直到找到目標節(jié)點。這個過程用數(shù)組記錄遇到的元素。
• step 2：分別在搜索二叉樹中找到p和q兩個點，并記錄各自的路徑為數(shù)組。
• step 3：同時遍歷兩個數(shù)組，比較元素值，最后一個相等的元素就是最近的公共祖先。

---

圖示過程解析：

---

代碼編寫：

---

---

二、用兩個棧實現(xiàn)隊列

題目描述

描述：

用兩個棧來實現(xiàn)一個隊列，使用n個元素來完成 n 次在隊列尾部插入整數(shù)(push)和n次在隊列頭部刪除整數(shù)(pop)的功能。 隊列中的元素為int類型。保證操作合法，即保證pop操作時隊列內(nèi)已有元素。

---

數(shù)據(jù)范圍：n≤1000；

要求：存儲n個元素的空間復雜度為 O(n)?，插入與刪除的時間復雜度都是 O(1)。

---

示例1：

---

示例2：

---

解題分析

解題思路：

雙棧法（推薦使用）

思路：

元素進棧以后，只能優(yōu)先彈出末尾元素，但是隊列每次彈出的卻是最先進去的元素，如果能夠?qū)Ｖ性厝咳〕鰜?#xff0c;才能訪問到最前面的元素，此時，可以用另一個棧來輔助取出。

---

解題步驟：

• step 1：push操作就正常push到第一個棧末尾。
• step 2：pop操作時，優(yōu)先將第一個棧的元素彈出，并依次進入第二個棧中。

• //將第一個棧中內(nèi)容彈出放入第二個棧中
  while(!stack1.isEmpty()) stack2.push(stack1.pop()); 
  

• step 3：第一個棧中最后取出的元素也就是最后進入第二個棧的元素就是隊列首部元素，要彈出，此時在第二個棧中可以直接彈出。
• step 4：再將第二個中保存的內(nèi)容，依次彈出，依次進入第一個棧中，這樣第一個棧中雖然取出了最里面的元素，但是順序并沒有變。

• //再將第二個棧的元素放回第一個棧
  while(!stack2.isEmpty()) stack1.push(stack2.pop());
  

  ---

圖示過程解析：

---

代碼編寫：

總結(jié)