作者簡(jiǎn)介：大家好，我是未央；

博客首頁(yè)：未央.303

系列專(zhuān)欄：?？兔嬖嚤厮OP101

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

文章目錄

前言

一、二叉搜索樹(shù)的最近公共祖先

題目描述

解題分析

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

題目描述

解題分析

總結(jié)

---

前言

一、二叉搜索樹(shù)的最近公共祖先

題目描述

描述：

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

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

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

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

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

---

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

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

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

---

舉例說(shuō)明：

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

---

示例1：

---

示例2：

解題分析

解題思路：
二叉搜索樹(shù)的定義：

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

圖示舉例說(shuō)明：

---

思路：

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

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

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

---

解題步驟：

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

---

圖示過(guò)程解析：

---

代碼編寫(xiě)：

---

---

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

題目描述

描述：

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

---

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

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

---

示例1：

---

示例2：

---

解題分析

解題思路：

雙棧法（推薦使用）

思路：

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

---

解題步驟：

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

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

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

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

  ---

圖示過(guò)程解析：

---

代碼編寫(xiě)：

總結(jié)