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

博客首頁：未央.303

系列專欄：?？兔嬖嚤厮OP101

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

文章目錄

前言

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

題目描述

解題分析

二、用兩個棧實(shí)現(xiàn)隊(duì)列

題目描述

解題分析

總結(jié)

---

前言

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

題目描述

描述：

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

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

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

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

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

---

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

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

0<=節(jié)點(diǎn)值<=10000

---

舉例說明：

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

---

示例1：

---

示例2：

解題分析

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

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

圖示舉例說明：

---

思路：

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

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

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

---

解題步驟：

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

---

圖示過程解析：

---

代碼編寫：

---

---

二、用兩個棧實(shí)現(xiàn)隊(duì)列

題目描述

描述：

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

---

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

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

---

示例1：

---

示例2：

---

解題分析

解題思路：

雙棧法（推薦使用）

思路：

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

---

解題步驟：

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

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

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

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

  ---

圖示過程解析：

---

代碼編寫：

總結(jié)