看了齊姐這篇文章，再也不怕面試問樹了

我們今天先來看，什么是“樹”。

樹是由頂點(diǎn)和邊組成的且不存在環(huán)的數(shù)據(jù)結(jié)構(gòu)。作為一個(gè)應(yīng)用非常廣的數(shù)據(jù)結(jié)構(gòu)，不僅在工作中常用，在面試中也非常?？?。????

一是因?yàn)闃涞慕Y(jié)構(gòu)天然決定了它和遞歸聯(lián)系緊密，很多樹相關(guān)的算法題都非常適合用遞歸來解；

二是因?yàn)樗碾y度介于鏈表和圖之間，非常適合在 45 分鐘的面試?yán)镞M(jìn)行考察，所以一場(chǎng)面試中遇到兩三輪問樹都是再正常不過的了。

本文先來講樹的基礎(chǔ)內(nèi)容，分為以下小節(jié)，每個(gè)小節(jié)開頭都會(huì)有思維導(dǎo)圖和對(duì)應(yīng)的 Leetcode 算法題喲～

1. 簡(jiǎn)介
2. 金融里的二叉樹
3. 樹的所有概念
   a. 樹的三大特點(diǎn)
   b. 樹的五大品種
   c. 高度和深度
4. 看樹的角度
   a. 三種 DFS 遍歷方式
   b. 兩種 BFS 遍歷方式
   c. 四種視圖

鑒于樹相關(guān)的內(nèi)容太多，而且又是面試重點(diǎn)內(nèi)容，之后會(huì)有文章再專門來講樹有關(guān)的解題思路以及最常用的二叉搜索樹，大家敬請(qǐng)期待～

簡(jiǎn)介

其實(shí)數(shù)據(jù)結(jié)構(gòu)里的“樹”和我們現(xiàn)實(shí)世界里的樹挺像的，只不過倒過來了嘛，根朝上。

比如：

在這片森林里，最常用的還是「二叉樹」。

二叉樹，是由很多個(gè) TreeNode 構(gòu)成的這種樹形的數(shù)據(jù)結(jié)構(gòu)，

class?TreeNode?{
????int?value;
????TreeNode?left;
????TreeNode?right;
}

就像鏈表中的 ListNode。

二叉樹并不一定非得是“二叉”的，而是說每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子，叫 left 和 right，但也可以沒有。

當(dāng)每個(gè)節(jié)點(diǎn)都只有一個(gè)孩子的時(shí)候，就退化成了鏈表。

所以鏈表就是一棵特殊的樹，而樹是一個(gè)特殊的圖。

金融里的二叉樹

大家知道我是金融背景的，所以我最開始了解二叉樹是在金融工程課程中給衍生品定價(jià)，這里也簡(jiǎn)單梳理下，不感興趣的小伙伴可以跳過這一段。

在金融工程里，二叉樹是用來在風(fēng)險(xiǎn)中性世界里給期權(quán)定價(jià)使用的模型。

比如這是一個(gè)股價(jià)二叉樹，其實(shí)就是我們把二叉樹放倒了看嘛。

上圖是兩期的二叉樹，那么最簡(jiǎn)單的一期的二叉樹定價(jià)模型表示為：

我們假設(shè)當(dāng)前股票的價(jià)格為 S，那我們想知道未來某個(gè)時(shí)刻比如 t 時(shí)刻的價(jià)格，股價(jià)有可能上漲也有可能下跌，還可能不變呢。

在該模型里我們就抽象成兩種可能性，一種是上漲，一種是下跌，所以可以用二叉樹來表示。

假設(shè)股票價(jià)格會(huì)有 p 的概率上漲至 uS,
有 1-p 的概率下跌至 dS.

這里的 p 并不是在真實(shí)世界里股票上漲的概率，而是一個(gè)在風(fēng)險(xiǎn)中性世界里的上漲概率，所以

股票現(xiàn)在的價(jià)格就是未來某時(shí)刻的無風(fēng)險(xiǎn)收益的折現(xiàn)，

即：

這就是最簡(jiǎn)單的二叉樹定價(jià)模型。

那我們言歸正傳。

樹的所有概念

1. 三大特點(diǎn)

樹的三大特點(diǎn)是：

1. 如果把樹看成一個(gè)無向圖，那么它是一個(gè)連通圖 connected graph.

2. 樹是一個(gè)無環(huán)圖。

3. 樹的節(jié)點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)之間的關(guān)系是固定的。如果樹上有 n 個(gè) node，那么它有 n-1 條邊。因?yàn)槌烁?jié)點(diǎn)，其他的節(jié)點(diǎn)都會(huì)有一條邊指向它。

2. 樹的品種

2.1 平衡二叉樹 Balanced Binary Tree：

• 定義：對(duì)于這棵樹里的每個(gè)節(jié)點(diǎn)，它的左子樹和右子樹的高度差不大于 1。

這里要注意，是對(duì)于每個(gè)節(jié)點(diǎn)，而不只是對(duì)于根結(jié)點(diǎn)。

比如左邊這棵樹就不是平衡二叉樹，右邊的才是。

那么大名鼎鼎的 AVL-Tree 就是平衡二叉樹，準(zhǔn)確說是自平衡二叉查找樹。

那什么是二叉查找樹呢？

2.2 二叉查找樹 Binary Search Tree

• 定義：對(duì)于這棵樹里的每個(gè)節(jié)點(diǎn)，
• 它左子樹里的每個(gè)節(jié)點(diǎn)的值都小于它的值；
• 它右子樹里的每個(gè)節(jié)點(diǎn)的值都大于它的值。

對(duì)二叉查找樹，最重要的性質(zhì)就是：

在做中序遍歷時(shí)，這個(gè)序列是一個(gè)升序序列。

當(dāng)你在做二叉查找樹的算法題沒有思路時(shí)，可以想想這個(gè)性質(zhì)，很多題目都會(huì)迎刃而解。

2.3 完全二叉樹 Complete Binary Tree：

• 定義：除了最后一層，其他層都是滿的，那么最后一層的節(jié)點(diǎn)要靠左排列且中間不允許有氣泡。

比如左邊不是完全二叉樹，右邊的是。

比如堆就是一個(gè)完全二叉樹，還不了解堆的基本操作的，公眾號(hào)內(nèi)回復(fù)「堆」獲取文章復(fù)習(xí)喲～

那么完全二叉樹的最大的好處就是因?yàn)樗帕芯o密沒有氣泡，所以可以用數(shù)組來存儲(chǔ)，這樣就大大節(jié)省了內(nèi)存空間。

2.4 完美二叉樹 Perfect Binary Tree

• 定義：所有層的所有節(jié)點(diǎn)都必須是滿的。

完美二叉樹比完全二叉樹的定義更加嚴(yán)格，包括最后一層，每一層的節(jié)點(diǎn)都要是滿的，畢竟是追求完美的嘛。

所以我們?nèi)绻懒藢訑?shù)，就知道了它有多少個(gè)節(jié)點(diǎn)，也就是一個(gè)等比數(shù)列求和。

2.5 完滿二叉樹 Full Tree

• 定義：對(duì)于這棵樹的每個(gè)節(jié)點(diǎn)而言，要么有 0 個(gè)孩子，要么有 2 個(gè)孩子。

大家不要輕視這些概念哦，很多算法題都會(huì)直接考察，在本節(jié)的思維導(dǎo)圖里也附帶了 Leetcode 對(duì)應(yīng)的題目，電面時(shí)很喜歡考哦～

3. 高度和深度

樹的高度 height 和深度 depth 是兩個(gè)非常重要的概念，比如 Leetcode 104 和 111 就是專門求樹的高度的。

而這兩個(gè)概念是相反方向的，大體上呢，

• 高度是從當(dāng)前節(jié)點(diǎn)到葉子 ? 節(jié)點(diǎn)的；
• 深度是從當(dāng)前節(jié)點(diǎn)到根 ? 節(jié)點(diǎn)的。

高度 Height

• 定義：從該節(jié)點(diǎn)，到以該節(jié)點(diǎn)為根節(jié)點(diǎn)的這棵樹的最遠(yuǎn)的葉子結(jié)點(diǎn)的最長(zhǎng)距離。

核心是，從該節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)，有幾條邊。

這個(gè)概念在分析時(shí)空復(fù)雜度時(shí)非常常用，比如在樹上做一個(gè)遞歸復(fù)雜度是 O(height)。

為什么呢？

因?yàn)檫@個(gè)距離決定了在 call stack 上有多少層。

深度 Depth

• 定義：從這個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離。

這個(gè)概念用的比較少，是和高度方向相反的概念。

看樹的角度

俗話說，橫看成嶺側(cè)成峰，這句話用在這里太合適不過了。

對(duì)于樹的幾種遍歷方式想必大家都不陌生，這就是我所說的「嶺」；

而還有一種面試?？碱}是問 left/right/vertical/border view，也就是求樹的左視圖、右視圖、俯視圖、border view 這我沒找到中文翻譯。。這就是我所說的「峰」。

先來總圖：

嶺

最基本的三種遍歷就是

• 前序 pre order
• 中序 in order
• 后序 post order

其實(shí)這三種遍歷方式本質(zhì)都是一樣的，只是輸出/打印節(jié)點(diǎn)的順序不同罷了。

來看偽代碼吧：

public?void?traverse(TreeNode?node)?{
??if?(root?==?null)?{
????return;
??}
??//preOrder
??print(root.value);

??traverse(root.left);?//真正的遍歷

??//inOrder
??print(root.value);

??traverse(root.right);?//真正的遍歷

??//postOrder
??print(root.value);
}

真正的遍歷就這兩句話，無論是那種遍歷順序都是不變的，變的只是打印的順序罷了。

這三種遍歷都是深度優(yōu)先遍歷 DFS，而層序遍歷是廣度優(yōu)先遍歷 BFS。

DFS 和 BFS 都是圖的基本遍歷方式，我之后也會(huì)專門寫一篇。

那我們來看層序遍歷 level order traversal。

輸出 5 7 3 1 4.

參考 Leetcode 102 題。

也就是每一層按照從左到右的順序遍歷。

那么還有一種 Zigzag 的遍歷方式，就是一行從左到右，下一行從右到左這樣子。

輸出的就是 5 3 7 1 4.

參考 Leetcode 103 題。

峰

left/right/vertical/border view，也就是求樹的左視圖、右視圖、俯視圖，是非常愛考的一類題，它們是什么意思呢？

比如對(duì)于這棵樹，

左視圖 left view：

• 就是從左邊看的每層的第一個(gè)節(jié)點(diǎn)。
• [5, 7, 9]

右視圖 right view：

• 就是從右邊看的每層的第一個(gè)節(jié)點(diǎn)。
• [5, 3, 8]

這兩個(gè)應(yīng)該比較簡(jiǎn)單，在層序遍歷的時(shí)候保留我們需要的值就可以了。

當(dāng)然還有其他方法，比如前序遍歷可以做左視圖，但不是那么的直觀，因?yàn)槟氵€要判斷這個(gè)元素是否是當(dāng)前層的第一個(gè)。大家有想法的可以在群里交流喲。（提示：可以再加一個(gè)變量

俯視圖

這個(gè)視圖比前兩個(gè)稍微難一點(diǎn)，在北美面試中是很愛考的。

首先這個(gè)圖中有一個(gè)變量叫 column，根節(jié)點(diǎn)為 0，左孩子 - 1，右孩子 + 1。

俯視圖指的是，從上往下看這棵樹，把 column 相同的這些節(jié)點(diǎn)放在一個(gè) list 里，從上往下放，然后按照 column 從小到大的順序排出來。

所以對(duì)于這棵樹，它的俯視圖是：

[[7], [5, 9], [3], [8]]

這題就作為本文的思考題啦，不是很難，大家可以在評(píng)論區(qū)或者群里交流～

Border View

在講完前三種視圖之后，這個(gè) border view 想必大家都能猜出來意思了。

就是求這棵樹的“輪廓”。

比如還是這棵樹，它的 border view 就是：

5, 7, 9, 8, 3

這題的大體思路不難，但是細(xì)節(jié)很多，而且很多條件可能就像我給的這樣并沒有定義清楚，所以你需要和面試官不斷的 clarify 很多細(xì)節(jié)。

普通的思路可以用

左視圖 + 葉子結(jié)點(diǎn) + 反著的右視圖

來做，表面上來看需要做三遍遍歷，但是其實(shí)一遍遍歷就夠了，因?yàn)槲覄偛耪f過，DFS 遍歷時(shí)，哪種遍歷方式都是一樣的，只是在不同時(shí)間打印不同節(jié)點(diǎn)罷了。

好了，以上就是本文的全部?jī)?nèi)容，如果喜歡，記得點(diǎn)贊哦～