我們今天先來(lái)看，什么是“樹(shù)”。

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

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

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

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

簡(jiǎn)介

金融里的二叉樹(shù)

樹(shù)的所有概念
a. 樹(shù)的三大特點(diǎn)
b. 樹(shù)的五大品種
c. 高度和深度

看樹(shù)的角度
a. 三種?DFS?遍歷方式
b. 兩種?BFS?遍歷方式
c. 四種視圖

簡(jiǎn)介

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

比如：

在這片森林里，最常用的還是「二叉樹(shù)」

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

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

就像鏈表中的?ListNode。

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

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

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

金融里的二叉樹(shù)

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

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

有些小伙伴會(huì)發(fā)現(xiàn)，這里的節(jié)點(diǎn)好像少了很多，沒(méi)錯(cuò)，因?yàn)槲覀冏尮蓛r(jià)每次上漲和下跌的幅度保持不變，所以到第 n 層最多有 n 個(gè)節(jié)點(diǎn)，而不會(huì)像普通的二叉樹(shù)一樣按照等比序列增長(zhǎng)。

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

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

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

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

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

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

即：

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

那我們言歸正傳。

樹(shù)的所有概念

1. 三大特點(diǎn)

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

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

樹(shù)是一個(gè)無(wú)環(huán)圖。

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

2. 樹(shù)的品種

2.1 平衡二叉樹(shù)?Balanced Binary Tree：

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

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

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

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

那什么是二叉查找樹(shù)呢？

2.2 二叉查找樹(shù)?Binary Search Tree

• 定義：對(duì)于這棵樹(shù)里的每個(gè)節(jié)點(diǎn)，

  • 它左子樹(shù)里的每個(gè)節(jié)點(diǎn)的值都小于它的值；

  • 它右子樹(shù)里的每個(gè)節(jié)點(diǎn)的值都大于它的值。

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

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

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

2.3 完全二叉樹(shù)?Complete Binary Tree：

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

比如左邊不是完全二叉樹(shù)，右邊的是。

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

2.4 完美二叉樹(shù)?Perfect Binary Tree

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

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

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

2.5 完滿二叉樹(shù)?Full Tree

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

3. 高度和深度

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

而這兩個(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)的這棵樹(shù)的最遠(yuǎn)的葉子結(jié)點(diǎn)的最長(zhǎng)距離。

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

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

為什么呢？

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

深度?Depth

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

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

看樹(shù)的角度

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

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

而還有一種面試常考題是問(wèn)?left/right/vertical/border view，也就是求樹(shù)的左視圖、右視圖、俯視圖、border view 這我沒(méi)找到中文翻譯。。這就是我所說(shuō)的「峰」。

先來(lái)總圖：

嶺

最基本的三種遍歷就是

• 前序?pre order

• 中序?in order

• 后序?post order

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

來(lái)看偽代碼吧：

public?void?traverse(TreeNode?node)?{if?(root?==?null)?{return;}//preOrderprint(root.value);traverse(root.left);?//真正的遍歷//inOrderprint(root.value);traverse(root.right);?//真正的遍歷//postOrderprint(root.value); }

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

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

DFS?和?BFS?都是圖的基本遍歷方式，我之后也會(huì)專(zhuān)門(mén)寫(xiě)一篇。

那我們來(lái)看層序遍歷?level order traversal。

輸出?5 7 3 1 4.

參考 Leetcode 102 題。

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

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

輸出的就是?5 3 7 1 4.

參考 Leetcode 103 題。

峰

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

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

左視圖?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)，在北美面試中是很愛(ài)考的。

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

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

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

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

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

Border View

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

就是求這棵樹(shù)的“輪廓”。

比如還是這棵樹(shù)，它的?border view?就是：

5, 7, 9, 8, 3

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

普通的思路可以用

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

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

總結(jié)

以上是生活随笔為你收集整理的面试常考的树，我这样讲给你听！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。