點選上方 三分鐘學前端，關注公衆号
回複交流，加入前端程式設計面試算法每日一題群
面試官也在看的前端面試資料
引言
不同與我們之前介紹的線性結構，今天我們介紹一種非線性結構：樹，本章重點介紹樹與二叉樹的基礎必會内容，在開始這一章節前，請思考以下内容：
- 什麼是樹？
- 什麼是二叉樹？
- 什麼是平衡二叉樹？
- 在代碼中如何表示一棵二叉樹？
- 二叉樹的前序、中序、後序周遊又是什麼？如何實作？能否用遞歸及疊代兩種方式實作喃？
- 什麼是 BST 樹？
- 什麼是 AVL 樹？
- 什麼是紅黑樹？
- 什麼是 Trie 樹？
- 什麼是 B 、B+ 樹？
下面進入本節内容????
8.1 樹
不同于我們上面介紹的線性結構，樹是一種非線性結構。
圖：
它遵循：
- 僅有唯一一個根節點，沒有節點則為空樹
- 除根節點外，每個節點都有并僅有唯一一個父節點
- 節點間不能形成閉環
這就是樹！
樹有幾個概念：
- 擁有相同父節點的節點，互稱為兄弟節點
- 節點的深度 ：從根節點到該節點所經曆的邊的個數
- 節點的高度 ：節點到葉節點的最長路徑
- 樹的高度：根節點的高度
B、C、D就互稱為兄弟節點，其中，節點B的高度為2，節點B的深度為 1，樹的高度為3
高度
樹的高度計算公式：
下圖每個節點值都代表來目前節點的高度：
8.2 二叉樹
二叉樹，故名思義，最多僅有兩個子節點的樹（最多能分兩個叉的樹????♀️）：
圖：
8.3 平衡二叉樹
二叉樹中，每一個節點的左右子樹的高度相差不能大于 1，稱為平衡二叉樹。
另外還有滿二叉樹、完全二叉樹等：
- 滿二叉樹：除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹
- 完全二叉樹：深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h 層所有的結點都連續集中在最左邊
8.4 在代碼中如何去表示一棵二叉樹
8.4.1 鍊式存儲法
二叉樹的存儲很簡單，在二叉樹中，我們看到每個節點都包含三部分：
- 目前節點的 val
- 左子節點 left
- 右子節點 right
是以我們可以将每個節點定義為：
function Node(val) {
// 儲存目前節點 key 值
this.val = val
// 指向左子節點
this.left = null
// 指向右子節點
this.right = null
}
一棵二叉樹可以由根節點通過左右指針連接配接起來形成一個樹。
function BinaryTree() {
let Node = function (val) {
this.val = val
this.left = null
this.right = null
}
let root = null
}
8.4.2 數組存儲法（适用于完全二叉樹）
下圖就是一棵完全二叉樹，
如果我們把根節點存放在位置
i=1
的位置，則它的左子節點位置為
2i = 2
，右子節點位置為
2i+1 = 3
。
如果我們選取 B 節點
i=2
，則它父節點為
i/2 = 1
，左子節點
2i=4
，右子節點
2i+1=5
。
以此類推，我們發現所有的節點都滿足這三種關系：
- 位置為 i 的節點，它的父節點位置為
i/2
- 它的左子節點
2i
- 它的右子節點
2i+1
是以，如果我們把完全二叉樹存儲在數組裡（從下标為 1 開始存儲），我們完全可以通過下标找到任意節點的父子節點。進而完整的建構出這個完全二叉樹。這就是數組存儲法。
數組存儲法相對于鍊式存儲法不需要為每個節點建立它的左右指針，更為節省記憶體。
8.5 二叉樹的周遊
二叉樹的周遊可分為：
- 前序周遊
- 中序周遊
- 後序周遊
所謂前、中、後，不過是根的順序，即也可以稱為先根周遊、中根周遊、後根周遊
1. 前序周遊
對于二叉樹中的任意一個節點，先列印該節點，然後是它的左子樹，最後右子樹
2. 中序周遊
對于二叉樹中的任意一個節點，先列印它的左子樹，然後是該節點，最後右子樹
3. 後序周遊
對于二叉樹中的任意一個節點，先列印它的左子樹，然後是右子樹，最後該節點
4. 代碼實作（前序周遊為例）
是以，周遊二叉樹的過程也就是一個遞歸的過程，例如前序周遊，先周遊根節點，然後是根的左子樹，最後右子樹；周遊根節點的左子樹的時候，又是先周遊左子樹的根節點，然後左子樹的左子樹，左子樹的右子樹…….
是以，它的核心代碼就是：
// 前序周遊核心代碼
const preOrderTraverseNode = (node) => {
if(node) {
// 先根節點
result.push(node.val)
// 然後周遊左子樹
preOrderTraverseNode(node.left)
// 再周遊右子樹
preOrderTraverseNode(node.right)
}
}
完整代碼如下：
遞歸實作
// 前序周遊
const preorderTraversal = (root) => {
let result = []
var preOrderTraverseNode = (node) => {
if(node) {
// 先根節點
result.push(node.val)
// 然後周遊左子樹
preOrderTraverseNode(node.left)
// 再周遊右子樹
preOrderTraverseNode(node.right)
}
}
preOrderTraverseNode(root)
return result
};
我們既然可以使用遞歸實作，那麼是否也可以使用疊代實作喃？
疊代實作
利用棧來記錄周遊的過程，實際上，遞歸就使用了調用棧，是以這裡我們可以使用棧來模拟遞歸的過程
- 首先根入棧
- 将根節點出棧，将根節點值放入結果數組中
- 然後周遊左子樹、右子樹，因為棧是先入後出，是以，我們先右子樹入棧，然後左子樹入棧
- 繼續出棧（左子樹被出棧）…….
依次循環出棧周遊入棧，直到棧為空，周遊完成
// 前序周遊
const preorderTraversal = (root) => {
const list = [];
const stack = [];
// 當根節點不為空的時候，将根節點入棧
if(root) stack.push(root)
while(stack.length > 0) {
const curNode = stack.pop()
// 第一步的時候，先通路的是根節點
list.push(curNode.val)
// 我們先列印左子樹，然後右子樹
// 是以先加入棧的是右子樹，然後左子樹
if(curNode.right !== null) {
stack.push(curNode.right)
}
if(curNode.left !== null) {
stack.push(curNode.left)
}
}
return list
}
複雜度分析：
空間複雜度：O(n)
時間複雜度：O(n)
至此，我們已經實作了二叉樹的前序周遊，嘗試思考一下二叉樹的中序周遊如何實作喃？
8.6 二叉查找樹（BST樹）
有的筆者也稱它為二叉搜尋樹，都是一個意思。
二叉樹本身沒有多大的意義，直到有位大佬提出一個 trick。
如果我們規定一顆二叉樹上的元素擁有順序，所有比它小的元素在它的左子樹，比它大的元素在它的右子樹，那麼我們不就可以很快地查找某個元素了嗎？
不得不說這是一個非常天才的想法，于是，二叉查找樹誕生了。
是以，二叉查找樹與二叉樹不同的是，它在二叉樹的基礎上，增加了對二叉樹上節點存儲位置的限制：二叉搜尋樹上的每個節點都需要滿足：
- 左子節點值小于該節點值
- 右子節點值大于等于該節點值
在二叉樹中，所有子節點值都是沒有固定規律的，是以使用二叉樹存儲結構存儲資料時，查找資料的時間複雜度為 O(n)，因為它要查找每一個節點。
而使用二叉查找樹就不同了，例如上圖，我們如果要查找 6 ，先從根節點 10 比較，6 比 10 小，則查找左子樹，再與 8 比較，6 比 8 小，繼續查找 8 的左子樹，也就是 6，我們找到了元素，結束。
8.6.1 基本操作
function BinarySearchTree() {
let Node = function (key) {
this.key = key
this.left = null
this.right = null
}
let root = null
// 插入
this.insert = function(key){}
// 查找
this.search = function(key){}
// 删除
this.remove = function(key){}
// 最大值
this.max = function(){}
// 最小值
this.min = function(){}
// 中序周遊
this.inOrderTraverse = function(){}
// 先序周遊
this.preOrderTraverse = function(){}
// 後序周遊
this.postOrderTraverse = function(){}
}
插入：
- 首先建立一個新節點
- 判斷樹是否為空，為空則設定插入的節點為根節點，插入成功，傳回
- 如果不為空，則比較該節點與根結點，比根小，插入左子樹，否則插入右子樹
function insert(key) {
// 建立新節點
let newNode = new Node(key)
// 判斷是否為空樹
if(root === null) {
root = newNode
} else {
insertNode(root, newNode)
}
}
// 将 insertNode 插入到 node 子樹上
function insertNode(node, newNode) {
if(newNode.key < node.key) {
// 插入 node 左子樹
if(node.left === null) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
// 插入 node 右子樹
if(node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
最值：
最小值：樹最左端的節點
最大值：樹最右端的節點
// 最小值
function min() {
let node = root
if(node) {
while(node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}
// 最大值
function max() {
let node = root
if(node) {
while(node && node.right !== null) {
node = node.right
}
return node.key
}
return null
}
查找：
function search(key) {
return searchNode(root, key)
}
function searchNode(node, key) {
if(node === null)
return false
if(key < node.key) {
return searchNode(node.left, key)
} else if(key > node.key) {
return searchNode(node.right, key)
} else {
return true
}
}
删除：
function remove(key) {
root = removeNode(root, key)
}
function removeNode(node, key) {
if(node === null)
return null
if(key < node.key) {
return removeNode(node.left, key)
} else if(key > node.key) {
return removeNode(node.right, key)
} else {
// key = node.key 删除
//葉子節點
if(node.left === null && node.right === null) {
node = null
return node
}
// 隻有一個子節點
if(node.left === null) {
node = node.right
return node
}
if(node.right === null) {
node = node.left
return node
}
// 有兩個子節點
// 擷取右子樹的最小值替換目前節點
let minRight = findMinNode(node.right)
node.key = minRight.key
node.right = removeNode(node.right, minRight.key)
return node
}
}
// 擷取 node 樹最小節點
function findMinNode(node) {
if(node) {
while(node && node.right !== null) {
node = node.right
}
return node
}
return null
}
8.6.2 周遊
中序周遊：
顧名思義，中序周遊就是把根放在中間的周遊，即按先左節點、然後根節點、最後右節點（左根右）的周遊方式。
由于BST樹任意節點都大于左子節點值小于等于右子節點值的特性，是以 中序周遊其實是對????進行排序操作 ，并且是按從小到大的順序排序。
function inOrderTraverse(callback) {
inOrderTraverseNode(root, callback)
}
function inOrderTraverseNode(node, callback) {
if(node !== null) {
// 先周遊左子樹
inOrderTraverseNode(node.left, callback)
// 然後根節點
callback(node.key)
// 再周遊右子樹
inOrderTraverseNode(node.right, callback)
}
}
// callback 每次将周遊到的結果列印到控制台
function callback(key) {
console.log(key)
}
先序周遊：
已經實作的中序周遊，先序周遊就很簡單了，它是按根左右的順序周遊
function preOrderTraverse() {
preOrderTraverseNode(root, callback)
}
function preOrderTraverseNode(node, callback) {
if(node !== null) {
// 先根節點
callback(node.key)
// 然後周遊左子樹
preOrderTraverseNode(node.left, callback)
// 再周遊右子樹
preOrderTraverseNode(node.right, callback)
}
}
// callback 每次将周遊到的結果列印到控制台
function callback(key) {
console.log(key)
}
後序周遊：
後序周遊按照左右根的順序周遊，實作也很簡單。
function postOrderTraverse() {
postOrderTraverseNode(root, callback)
}
function postOrderTraverseNode(node, callback) {
if(node !== null) {
// 先周遊左子樹
postOrderTraverseNode(node.left, callback)
// 然後周遊右子樹
postOrderTraverseNode(node.right, callback)
// 最後根節點
callback(node.key)
}
}
// callback 每次将周遊到的結果列印到控制台
function callback(key) {
console.log(key)
}
8.6.3 BST樹的局限
在理想情況下，二叉樹每多一層，可以存儲的元素都增加一倍。也就是說 n 個元素的二叉搜尋樹，對應的樹高為 O(logn)。是以我們查找元素、插入元素的時間也為 O(logn)。
當然這是理想情況下，但在實際應用中，并不是那麼理想，例如一直遞增或遞減的給一個二叉查找樹插入資料，那麼所有插入的元素就會一直出現在一個樹的左節點上，數型結構就會退化為連結清單結構，時間複雜度就會趨于 O(n)，這是不好的。
而我們上面的平衡樹就可以很好的解決這個問題，是以平衡二叉查找樹（AVL樹，下一章節探讨）由此誕生。
8.7 平衡二叉查找樹（AVL樹）
故名思義，既滿足左右子樹高度不大于 1， 又滿足任意節點值大于它的左子節點值，小于等于它的右子節點值。
AVL 這個名字的由來，是它的兩個發明者G. M. Adelson-Velsky 和 Evgenii Landis 的縮寫，AVL最初是他們兩人在1962 年的論文「An algorithm for the organization of information」中提出來一種資料結構
8.8 紅黑樹
紅黑樹也是一種特殊的「二叉查找樹」。
到目前為止我們學習的 AVL 樹和即将學習的紅黑樹都是二叉查找樹的變體，可見二叉查找樹真的是非常重要基礎二叉樹，如果忘了它的定義可以先回頭看看。
紅黑樹是一種比較難的資料結構，面試中很少有面試官讓你手寫一個紅黑樹，最多的話是考察你是否了解紅黑樹，以及為什麼有了 AVL 樹還需要紅黑樹，本部分就主要介紹這塊。
8.8.1 什麼是紅黑樹
紅黑樹是一種自平衡（并不是絕對平衡）的二叉查找樹，它除了滿足二分查找樹的特點外，還滿足以下條件：
- 節點是紅色或黑色
- 根節點必須是黑色節點
- 所有的葉子節點都必須是值為 NULL 的黑節點
- 如果一個節點是紅色的，則它兩個子節點都是黑色的
- 從任一節點到達它的每個葉子節點的所有的路徑，都有相同數目的黑色節點
很多人不了解為神馬要有那麼多條條框框，這裡引用王争老師的說法：
我們都玩過魔方吧，其實魔方的複原是有固定算法的，遇到哪幾面是什麼樣的，你就對應轉幾下，隻要跟着這個複原步驟，最終肯定能把魔方複原。紅黑樹也是的，它也有固定的條條框框，在插入、删除時也有固定的調整方案。
這些條條框框保證紅黑樹的自平衡，保證紅黑樹從根節點到達每一個葉子節點的最長路徑不會超過最短路徑的 2 倍。
而節點的路徑長度決定着對節點的查詢效率，這樣我們確定了，最壞情況下的查找、插入、删除操作的時間複雜度不超過 O(logn) ，并且有較高的插入和删除效率。
8.8.2 紅黑樹 VS 平衡二叉樹（AVL樹）
- 插入和删除操作，一般認為紅黑樹的删除和插入會比 AVL 樹更快。因為，紅黑樹不像 AVL 樹那樣嚴格的要求平衡因子小于等于1，這就減少了為了達到平衡而進行的旋轉操作次數，可以說是犧牲嚴格平衡性來換取更快的插入和删除時間。
- 紅黑樹不要求有不嚴格的平衡性控制，但是紅黑樹的特點，使得任何不平衡都會在三次旋轉之内解決。而 AVL 樹如果不平衡，并不會控制旋轉操作次數，旋轉直到平衡為止。
- 查找操作，AVL樹的效率更高。因為 AVL 樹設計比紅黑樹更加平衡，不會出現平衡因子超過 1 的情況，減少了樹的平均搜尋長度。
8.9 Trie 樹
8.9.1 什麼是 Trie 樹
Trie 樹，也稱為字典樹或字首樹，顧名思義，它是用來處理字元串比對問題的資料結構，以及用來解決集合中查找固定字首字元串的資料結構。
8.9.2 Trie樹的應用：字元串比對
在搜尋引擎中輸入關鍵字，搜尋引擎都會彈出下拉框，顯示各種關鍵字提示，例如必應：
必應是如何處理這一過程的喃？
或者，假設我們有n個單詞的資料集，任意輸入一串字元，如何在資料集中快速比對出具有輸入字元字首的單詞？
這樣類似的問題還有很多，在日常開發中，遇到類似的問題，我們應該如何去處理？選擇怎樣的資料結構與算法？尤其是遇到大規模資料時，如何更高效的處理？
最簡單的方法就是暴力，将資料集中的每個字元串，逐個字元的比對輸入字元，所有字元都比對上則字首比對成功。這種方式也是我們開發當中最常用，最簡單的方式，時間複雜度為
O(m*n)
，其中
m
為輸入字元串長度，
n
為資料集規模。
這個時間複雜度是很高的，當
n
很大時，暴力法性能就會很差，此時必須重新尋找合适的算法。
我們知道在樹上查找、插入都比較友善，一般時間複雜度隻與樹的高度相關，我們可以通過樹結構來處理，也就是我們要說的 Trie 樹。其實，引擎搜尋關鍵字提示底層也是通過 Trie 樹實作的。
舉個例子：假設資料集有：
are
、
add
、
adopt
、
set
、
so
，它構鍵過程：
當是以的字元串插入完成，Trie樹就建構完成了。
Trie樹的本質是利用字元串的公共字首，将重複的字首合并在一起，其中根節點不包含任何資訊，每個節點表示一個字元串中的字元，從根節點到葉節點的路徑，表示一個字元串。
在字元串比對的時候，我們隻要按照樹的結構從上到下比對即可。
8.10 B 樹、B+ 樹（感興趣進）
8.10.1 多叉查找樹
既然二叉查找樹已經了解了，那多叉查找樹就很好了解了，它與二叉查找樹唯一不同的是，它是多叉的。也就是說，多叉查找樹允許一個節點存儲多個元素，并且可以擁有多個子樹。
為什麼在有二叉查找樹的情況下，還要有多叉查找樹喃？
我們知道樹的深度越高，時間複雜度越高，性能越差，多叉查找樹相對于二叉查找樹來說，每個節點不止能擁有兩個子節點，每層存放的節點數可比二叉查找樹多，自然多叉查找樹的的深度就要更小，性能也就更好。例如主要用于各大存儲檔案系統與資料庫系統中的 B 樹。
8.10.2 B 樹(B-tree)
B 樹，又稱平衡多叉查找樹。它是一種自平衡的多叉查找樹。
如果一棵多路查找樹滿足以下規則，則稱之為 B 樹：
- 排序方式：所有節點關鍵字是按遞增次序排列，并遵循左小右大原則；
- 子節點數：非葉節點的子節點數>1，且<=M ，且M>=2，空樹除外（注：M階代表一個樹節點最多有多少個查找路徑，M=M叉（或路），當M=2則是2叉樹，M=3則是3叉）；
- 關鍵字數：枝節點（非根非葉）的關鍵字數量（K）應滿足 (M+1)/2 < K < M
- 所有葉子節點均在同一層、葉子節點除了包含了關鍵字和關鍵字記錄的指針外也有指向其子節點的指針隻不過其指針位址都為null對應下圖最後一層節點的空格子;
最後，我們使用一張圖加深一下了解：
8.10.3 B+樹
B+樹與B樹一樣都是多叉平衡查找樹（又名多路平衡查找樹），B+樹與B樹不同的是：
-
B+樹改進了B樹，讓内結點（非葉節點）隻作索引使用，去掉了其中指向data的指針，使得每個結點中能夠存放更多的key， 是以能有更大的出度。
這有什麼用？這樣就意味着存放同樣多的key，樹的層高能進一步被壓縮，使得檢索的時間更短
- 中間節點的元素數量與子樹一緻，而B樹子樹數量與元素數量多1
- 葉子節點是一個連結清單，可以通過指針順序查找
8.11 加深
8.11.1 二叉樹的中序周遊
遞歸實作：
// 中序周遊
const inorderTraversal = (root) => {
let result = []
var inorderTraversal = (node) => {
if(node) {
// 先周遊左子樹
inorderTraversal(node.left)
// 再根節點
result.push(node.val)
// 最後周遊右子樹
inorderTraversal(node.right)
}
}
inorderTraversal(root)
return result
};
疊代實作：
const inorderTraversal = function(root) {
let list = []
let stack = []
let node = root
while(stack.length || node) {
if(node) {
stack.push(node)
node = node.left
continue
}
node = stack.pop()
list.push(node.val)
node = node.right
}
return list
};
進一步簡化：
// 中序周遊
const inorderTraversal = (root) => {
let list = []
let stack = []
let node = root
while(node || stack.length) {
// 周遊左子樹
while(node) {
stack.push(node)
node = node.left
}
node = stack.pop()
list.push(node.val)
node = node.right
}
return list
}
複雜度分析：
- 空間複雜度：O(n)
- 時間複雜度：O(n)
更多解答
8.11.2 二叉樹的後序周遊
遞歸實作
// 後序周遊
const postorderTraversal = function(root) {
let result = []
var postorderTraversalNode = (node) => {
if(node) {
// 先周遊左子樹
postorderTraversalNode(node.left)
// 再周遊右子樹
postorderTraversalNode(node.right)
// 最後根節點
result.push(node.val)
}
}
postorderTraversalNode(root)
return result
};
疊代實作
解題思路： 後序周遊與前序周遊不同的是：
- 後序周遊是左右根
- 而前序周遊是根左右
如果我們把前序周遊的
list.push(node.val)
變更為
list.unshift(node.val)
（周遊結果逆序），那麼周遊順序就由 根左右 變更為 右左根
然後我們僅需将 右左根 變更為 左右根 即可完成後序遍
// 後序周遊
const postorderTraversal = (root) => {
const list = [];
const stack = [];
// 當根節點不為空的時候，将根節點入棧
if(root) stack.push(root)
while(stack.length > 0) {
const node = stack.pop()
// 根左右=>右左根
list.unshift(node.val)
// 先進棧左子樹後右子樹
// 出棧的順序就變更為先右後左
// 右先頭插法入list
// 左再頭插法入list
// 實作右左根=>左右根
if(node.left !== null) {
stack.push(node.left)
}
if(node.right !== null) {
stack.push(node.right)
}
}
return list
}
複雜度分析：
- 空間複雜度：O(n)
- 時間複雜度：O(n)
更多解答
8.11.3 二叉樹的層次周遊
給定一個二叉樹，傳回其節點值自底向上的層次周遊。（即按從葉子節點所在層到根節點所在的層，逐層從左向右周遊）
例如：給定二叉樹
[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
傳回其自底向上的層次周遊為：
[
[15,7],
[9,20],
[3]
]
解法一：BFS（廣度優先周遊）
BFS 是按層層推進的方式，周遊每一層的節點。題目要求的是傳回每一層的節點值，是以這題用 BFS 來做非常合适。BFS 需要用隊列作為輔助結構，我們先将根節點放到隊列中，然後不斷周遊隊列。
const levelOrderBottom = function(root) {
if(!root) return []
let res = [],
queue = [root]
while(queue.length) {
let curr = [],
temp = []
while(queue.length) {
let node = queue.shift()
curr.push(node.val)
if(node.left) temp.push(node.left)
if(node.right) temp.push(node.right)
}
res.push(curr)
queue = temp
}
return res.reverse()
};
複雜度分析
- 時間複雜度：O(n)
- 空間複雜度：O(n)
解法二：DFS（深度優先周遊）
DFS 是沿着樹的深度周遊樹的節點，盡可能深地搜尋樹的分支
DFS 做本題的主要問題是：DFS 不是按照層次周遊的。為了讓遞歸的過程中同一層的節點放到同一個清單中，在遞歸時要記錄每個節點的深度
depth
。遞歸到新節點要把該節點放入
depth
對應清單的末尾。
當周遊到一個新的深度
depth
，而最終結果
res
中還沒有建立
depth
對應的清單時，應該在
res
中建立一個清單用來儲存該
depth
的所有節點。
const levelOrderBottom = function(root) {
const res = []
var dep = function (node, depth){
if(!node) return
res[depth] = res[depth]||[]
res[depth].push(node.val)
dep(node.left, depth + 1)
dep(node.right, depth + 1)
}
dep(root, 0)
return res.reverse()
};
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(h)，h為樹的高度
更多解答
8.11.4 二叉樹的層序周遊
給你一個二叉樹，請你傳回其按 層序周遊 得到的節點值。（即逐層地，從左到右通路所有節點）。
示例：二叉樹：
[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
傳回其層次周遊結果：
[
[3],
[9,20],
[15,7]
]
感謝 @plane-hjh 的解答：
這道題和二叉樹的層次周遊相似，隻需要把
reverse()
去除就可以了
廣度優先周遊
const levelOrder = function(root) {
if(!root) return []
let res = [],
queue = [root]
while(queue.length) {
let curr = [],
temp = []
while(queue.length) {
let node = queue.shift()
curr.push(node.val)
if(node.left) temp.push(node.left)
if(node.right) temp.push(node.right)
}
res.push(curr)
queue = temp
}
return res
};
深度優先周遊
const levelOrder = function(root) {
const res = []
var dep = function (node, depth){
if(!node) return
res[depth] = res[depth]||[]
res[depth].push(node.val)
dep(node.left, depth + 1)
dep(node.right, depth + 1)
}
dep(root, 0)
return res
};
更多解答
8.11.5 重構二叉樹：從前序與中序周遊序列構造二叉樹
輸入某二叉樹的前序周遊和中序周遊的結果，請重建該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。
注意:你可以假設樹中沒有重複的元素。
例如，給出
前序周遊 preorder = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]
傳回如下的二叉樹：
3
/ \
9 20
/ \
15 7
限制：
0 <= 節點個數 <= 5000
推薦 @luweiCN 的解答：
仔細分析前序周遊和中序周遊可以知道（以題目為例）：
- 前序周遊的第一個元素一定是根節點，這裡是
3
- 找到根節點之後，根節點在中序周遊中把數組一分為二，即兩個數組
[9]
[15, 20, 7]
3
- 前序周遊數組去掉根節點之後是
[9,20,15,7]
[9]
[20, 15, 7]
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
const buildTree = function (preorder, inorder) {
if (preorder.length) {
let head = new TreeNode(preorder.shift());
let index = inorder.indexOf(head.val);
head.left = buildTree(
preorder.slice(0, index),
inorder.slice(0, index)
);
head.right = buildTree(preorder.slice(index), inorder.slice(index + 1));
// 這裡要注意，preorder前面shift一次長度比inorder小1
return head;
} else {
return null;
}
};
更多解答
8.11.6 二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
說明: 葉子節點是指沒有子節點的節點。
示例：給定二叉樹
[3,9,20,null,null,15,7]
，
3
/ \
9 20
/ \
15 7
傳回它的最大深度 3
解答：遞歸
const maxDepth = function(root) {
if(!root) return 0
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(logn)
更多解答
8.11.7 二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
例如，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節點 5 和節點 1 的最近公共祖先是節點 3。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節點 5 和節點 4 的最近公共祖先是節點 5。因為根據定義最近公共祖先節點可以為節點本身。
說明:
- 所有節點的值都是唯一的。
- p、q 為不同節點且均存在于給定的二叉樹中。
解答：遞歸實作
解題思路：
如果樹為空樹或
p
、
q
中任一節點為根節點，那麼
p
、
q
的最近公共節點為根節點
如果不是，即二叉樹不為空樹，且
p
、
q
為非根節點，則遞歸周遊左右子樹，擷取左右子樹的最近公共祖先，
- 如果
p
q
p
q
root
- 若
p
q
p
q
p
q
- 若
p
q
p
q
- 如果
p
q
null
代碼實作：
const lowestCommonAncestor = function(root, p, q) {
if(root == null || root == p || root == q) return root
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
if(left === null) return right
if(right === null) return left
return root
};
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
更多解答
8.11.8 平衡二叉樹
給定一個二叉樹，判斷它是否是高度平衡的二叉樹。
本題中，一棵高度平衡二叉樹定義為：
一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。
示例 1:
給定二叉樹
[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
傳回
true
。
示例 2:
給定二叉樹
[1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
傳回
false
。
解答一：自頂向下（暴力法）
解題思路： 自頂向下的比較每個節點的左右子樹的最大高度差，如果二叉樹中每個節點的左右子樹最大高度差小于等于
1
，即每個子樹都平衡時，此時二叉樹才是平衡二叉樹
代碼實作：
const isBalanced = function (root) {
if(!root) return true
return Math.abs(depth(root.left) - depth(root.right)) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right)
}
const depth = function (node) {
if(!node) return -1
return 1 + Math.max(depth(node.left), depth(node.right))
}
複雜度分析：
- 時間複雜度：O(nlogn)，計算
depth
- 空間複雜度：O(n)
解答二：自底向上（優化）
解題思路： 利用後續周遊二叉樹（左右根），從底至頂傳回子樹最大高度，判定每個子樹是不是平衡樹 ，如果平衡，則使用它們的高度判斷父節點是否平衡，并計算父節點的高度，如果不平衡，傳回
-1
。
周遊比較二叉樹每個節點 的左右子樹深度：
- 比較左右子樹的深度，若內插補點大于
1
-1
- 左右子樹有一個不是平衡的，或左右子樹內插補點大于
1
- 若左右子樹平衡，傳回目前樹的深度（左右子樹的深度最大值
+1
代碼實作：
const isBalanced = function (root) {
return balanced(root) !== -1
};
const balanced = function (node) {
if (!node) return 0
const left = balanced(node.left)
const right = balanced(node.right)
if (left === -1 || right === -1 || Math.abs(left - right) > 1) {
return -1
}
return Math.max(left, right) + 1
}
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
更多解答
8.11.9 路徑總和
給定一個二叉樹和一個目标和，判斷該樹中是否存在根節點到葉子節點的路徑，這條路徑上所有節點值相加等于目标和。
說明: 葉子節點是指沒有子節點的節點。
示例: 給定如下二叉樹，以及目标和
sum = 22
，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
傳回
true
, 因為存在目标和為
22
的根節點到葉子節點的路徑
5->4->11->2
。
解題思路：
隻需要周遊整棵樹
- 如果目前節點不是葉子節點，遞歸它的所有子節點，傳遞的參數就是 sum 減去目前的節點值；
- 如果目前節點是葉子節點，判斷參數 sum 是否等于目前節點值，如果相等就傳回 true，否則傳回 false。
代碼實作：
var hasPathSum = function(root, sum) {
// 根節點為空
if (root === null) return false;
// 葉節點 同時 sum 參數等于葉節點值
if (root.left === null && root.right === null) return root.val === sum;
// 總和減去目前值，并遞歸
sum = sum - root.val
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
};
更多解答
8.11.10 對稱二叉樹
給定一個二叉樹，檢查它是否是鏡像對稱的。
例如，二叉樹
[1,2,2,3,4,4,3]
是對稱的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個
[1,2,2,null,3,null,3]
則不是鏡像對稱的:
1
/ \
2 2
\ \
3 3
進階：
你可以運用遞歸和疊代兩種方法解決這個問題嗎？
解答：
一棵二叉樹對稱，則需要滿足：根的左右子樹是鏡像對稱的
也就是說，每棵樹的左子樹都和另外一顆樹的右子樹鏡像對稱，左子樹的根節點值與右子樹的根節點值相等
是以，我們需要比較：
- 左右子樹的根節點值是否相等
- 左右子樹是否鏡像對稱
邊界條件：
- 左右子樹都為
null
true
- 左右子樹有一個
null
false
解法一：遞歸
const isSymmetric = function(root) {
if(!root) return true
var isEqual = function(left, right) {
if(!left && !right) return true
if(!left || !right) return false
return left.val === right.val
&& isEqual(left.left, right.right)
&& isEqual(left.right, right.left)
}
return isEqual(root.left, root.right)
};
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
解法二：疊代
利用棧來記錄比較的過程，實際上，遞歸就使用了調用棧，是以這裡我們可以使用棧來模拟遞歸的過程
- 首先根的左右子樹入棧
- 将左右子樹出棧，比較兩個數是否互為鏡像
- 如果左右子樹的根節點值相等，則将左子樹的
left
right
right
left
- 繼續出棧（一次出棧兩個進行比較）…….
依次循環出棧入棧，直到棧為空
const isSymmetric = function(root) {
if(!root) return true
let stack = [root.left, root.right]
while(stack.length) {
let right = stack.pop()
let left = stack.pop()
if(left && right) {
if(left.val !== right.val) return false
stack.push(left.left)
stack.push(right.right)
stack.push(left.right)
stack.push(right.left)
} else if(left || right) {
return false
}
}
return true
};
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(n)
劍指Offer&leetcode101：對稱二叉樹
8.11.11給定一個二叉樹, 找到該樹中兩個指定節點間的最短距離
function TreeNode(val) { this.val = val; this.left = this.right = null; }
解答：
求最近公共祖先節點，然後再求最近公共祖先節點到兩個指定節點的路徑，再求兩個節點的路徑之和
const shortestDistance = function(root, p, q) {
// 最近公共祖先
let lowestCA = lowestCommonAncestor(root, p, q)
// 分别求出公共祖先到兩個節點的路經
let pDis = [], qDis = []
getPath(lowestCA, p, pDis)
getPath(lowestCA, q, qDis)
// 傳回路徑之和
return (pDis.length + qDis.length)
}
// 最近公共祖先
const lowestCommonAncestor = function(root, p, q) {
if(root === null || root === p || root === q) return root
const left = lowestCommonAncestor(root.left, p, q)
const right = lowestCommonAncestor(root.right, p, q)
if(left === null) return right
if(right === null) return left
return root
}
const getPath = function(root, p, paths) {
// 找到節點，傳回 true
if(root === p) return true
// 目前節點加入路徑中
paths.push(root)
let hasFound = false
// 先找左子樹
if (root.left !== null)
hasFound = getPath(root.left, p, paths)
// 左子樹沒有找到，再找右子樹
if (!hasFound && root.right !== null)
hasFound = getPath(root.right, p, paths)
// 沒有找到，說明不在這個節點下面，則彈出
if (!hasFound)
paths.pop()
return hasFound
}
更多解答
8.11.12 二叉搜尋樹中第K小的元素
給定一個二叉搜尋樹，編寫一個函數
kthSmallest
來查找其中第
k
個最小的元素。
說明：你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜尋樹元素個數。
示例 1:
輸入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
輸出: 1
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
輸出: 3
進階：如果二叉搜尋樹經常被修改（插入/删除操作）并且你需要頻繁地查找第 k 小的值，你将如何優化 kthSmallest 函數？
解答：
我們知道：中序周遊其實是對????進行排序操作 ，并且是按從小到大的順序排序，是以本題就很簡單了
解題思路： 中序周遊二叉搜尋樹，輸出第 k 個既可
代碼實作（遞歸）：
const kthSmallest = function(root, k) {
let res = null
let inOrderTraverseNode = function(node) {
if(node !== null && k > 0) {
// 先周遊左子樹
inOrderTraverseNode(node.left)
// 然後根節點
if(--k === 0) {
res = node.val
return
}
// 再周遊右子樹
inOrderTraverseNode(node.right)
}
}
inOrderTraverseNode(root)
return res
}
複雜度分析：
- 時間複雜度：O(k)
- 空間複雜度：不考慮遞歸棧所占用的空間，空間複雜度為 O(1)
代碼實作（疊代）：
const kthSmallest = function(root, k) {
let stack = []
let node = root
while(node || stack.length) {
// 周遊左子樹
while(node) {
stack.push(node)
node = node.left
}
node = stack.pop()
if(--k === 0) {
return node.val
}
node = node.right
}
return null
}
複雜度分析：
- 時間複雜度：O(H+K)
- 空間複雜度：空間複雜度為 O(H+K)
更多解答
8.11.13 實作 Trie（字首樹）
實作一個 Trie (字首樹)，包含
insert
,
search
, 和
startsWith
這三個操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 傳回 true
trie.search("app"); // 傳回 false
trie.startsWith("app"); // 傳回 true
trie.insert("app");
trie.search("app"); // 傳回 true
說明:
- 你可以假設所有的輸入都是由小寫字母 a-z 構成的。
- 保證所有輸入均為非空字元串。
解答：
我們可以搭建一個初始 Trie 樹結構：
// Trie 樹
var Trie = function() {};
// 插入
Trie.prototype.insert = function(word) {};
// 搜尋
Trie.prototype.search = function(word) {};
// 字首比對
Trie.prototype.startsWith = function(prefix) {};
1. 如何存儲一個 Trie 樹
首先，我們需要實作一個 Trie 樹，我們知道，二叉樹的存儲（鍊式存儲）是通過左右指針來實作的，即二叉樹中的節點：
function BinaryTreeNode(key) {
// 儲存目前節點 key 值
this.key = key
// 指向左子節點
this.left = null
// 指向右子節點
this.right = null
}
在這裡，它不止有兩個位元組點，它最多有 a-z 總共有26個子節點。最簡單的實作是把她們儲存在一個字典裡：
-
isEnd
-
children
key:value
key
value
var TrieNode = function() {
// next 放入目前節點的子節點
this.next = {};
// 目前是否是結束節點
this.isEnd = false;
};
是以：
// Trie 樹
var Trie = function() {
this.root = new TrieNode()
};
2. 插入
- 首先判斷插入節點是否為空，為空則傳回
- 周遊待插入字元，從根節點逐字元查找 Trie 樹，如果字元查找失敗則插入，否則繼續查找下一個字元
- 待插入字元周遊完成，設定最後字元的
isEnd
true
- 傳回插入成功
Trie.prototype.insert = function(word) {
if (!word) return false
let node = this.root
for (let i = 0; i < word.length; i++) {
if (!node.next[word[i]]) {
node.next[word[i]] = new TrieNode()
}
node = node.next[word[i]]
}
node.isEnd = true
return true
};
3. 搜尋
Trie.prototype.search = function(word) {
if (!word) return false
let node = this.root
for (let i = 0; i < word.length; ++i) {
if (node.next[word[i]]) {
node = node.next[word[i]]
} else {
return false
}
}
return node.isEnd
};
4. 字首比對
Trie.prototype.startsWith = function(prefix) {
if (!prefix) return true
let node = this.root
for (let i = 0; i < prefix.length; ++i) {
if (node.next[prefix[i]]) {
node = node.next[prefix[i]]
} else {
return false
}
}
return true
};
最近開源了一個github倉庫：百問百答，在工作中很難做到對社群問題進行立即解答，是以可以将問題送出至 https://github.com/Advanced-Frontend/Just-Now-QA ，我會在每晚花費 1 個小時左右進行處理，更多的是鼓勵與歡迎更多人一起參與探讨與解答????
最後
歡迎關注「三分鐘學前端」，回複「交流」自動加入前端三分鐘進階群，每日一道程式設計算法面試題（含解答），助力你成為更優秀的前端開發！
号内回複：
「網絡」，自動擷取三分鐘學前端網絡篇小書（90+頁）
「JS」，自動擷取三分鐘學前端 JS 篇小書（120+頁）
「算法」，自動擷取 github 2.9k+ 的前端算法小書
「面試」，自動擷取 github 23.2k+ 的前端面試小書
「履歷」，自動擷取程式員系列的
120
套模版
》》面試官也在看的前端面試資料《《
“在看和轉發”就是最大的