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

2020 年 8 月 11 日
筆記
演算法和數據結構

在寫完了所有線性數據結構之後，今天開啟非線性數據結構系列。

我們今天先來看，什麼是「樹」。

樹是由頂點和邊組成的且不存在環的數據結構。作為一個應用非常廣的數據結構，不僅在工作中常用，在面試中也非常常考。

一是因為樹的結構天然決定了它和遞歸聯繫緊密，很多樹相關的演算法題都非常適合用遞歸來解；

二是因為它的難度介於鏈表和圖之間，非常適合在 45 分鐘的面試里進行考察，所以一場面試中遇到兩三輪問樹都是再正常不過的了。

本文先來講樹的基礎內容，分為以下小節，每個小節開頭都會有思維導圖和對應的 Leetcode 演算法題喲～

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

鑒於樹相關的內容太多，而且又是面試重點內容，之後會有文章再專門來講樹有關的解題思路以及最常用的二叉搜索樹，大家敬請期待～

簡介

其實數據結構里的「樹」和我們現實世界裡的樹挺像的，只不過倒過來了嘛，根朝上。

比如：

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

二叉樹，是由很多個 TreeNode 構成的這種樹形的數據結構，

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

就像鏈表中的 ListNode。

二叉樹並不一定非得是「二叉」的，而是說每個節點最多有兩個孩子，叫 left 和 right，但也可以沒有。

當每個節點都只有一個孩子的時候，就退化成了鏈表。

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

金融里的二叉樹

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

在金融工程里，二叉樹是用來在風險中性世界裡給期權定價使用的模型。

比如這是一個股價二叉樹，其實就是我們把二叉樹放倒了看嘛。

有些小夥伴會發現，這裡的節點好像少了很多，沒錯，因為我們讓股價每次上漲和下跌的幅度保持不變，所以到第 n 層最多有 n 個節點，而不會像普通的二叉樹一樣按照等比序列增長。

上圖是兩期的二叉樹，那麼最簡單的一期的二叉樹定價模型表示為：

我們假設當前股票的價格為 S，那我們想知道未來某個時刻比如 t 時刻的價格，股價有可能上漲也有可能下跌，還可能不變呢。

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

假設股票價格會有 p 的概率上漲至 uS,
有 1-p 的概率下跌至 dS.

這裡的 p 並不是在真實世界裡股票上漲的概率，而是一個在風險中性世界裡的上漲概率，所以

股票現在的價格就是未來某時刻的無風險收益的折現，

即：

$$S = e^{-rt}[pS_u + (1-p) S_d] $$

這就是最簡單的二叉樹定價模型。

那我們言歸正傳。

樹的所有概念

1. 三大特點

樹的三大特點是：

如果把樹看成一個無向圖，那麼它是一個連通圖 connected graph.
樹是一個無環圖。
樹的節點個數和邊的個數之間的關係是固定的。如果樹上有 n 個 node，那麼它有 n-1 條邊。因為除了根節點，其他的節點都會有一條邊指向它。

2. 樹的品種

2.1 平衡二叉樹 Balanced Binary Tree：

定義：對於這棵樹里的每個節點，它的左子樹和右子樹的高度差不大於 1。

這裡要注意，是對於每個節點，而不只是對於根結點。

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

那麼大名鼎鼎的 AVL-Tree 就是平衡二叉樹，準確說是自平衡二叉查找樹。

那什麼是二叉查找樹呢？

2.2 二叉查找樹 Binary Search Tree

定義：對於這棵樹里的每個節點，
- 它左子樹里的每個節點的值都小於它的值；
- 它右子樹里的每個節點的值都大於它的值。

對二叉查找樹，最重要的性質就是：

在做中序遍歷時，這個序列是一個升序序列。

當你在做二叉查找樹的演算法題沒有思路時，可以想想這個性質，很多題目都會迎刃而解。

2.3 完全二叉樹 Complete Binary Tree：

定義：除了最後一層，其他層都是滿的，那麼最後一層的節點要靠左排列且中間不允許有氣泡。

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

比如堆就是一個完全二叉樹，還不了解堆的基本操作的，公眾號內回復「堆」獲取文章複習喲～

那麼完全二叉樹的最大的好處就是因為它排列緊密沒有氣泡，所以可以用數組來存儲，這樣就大大節省了記憶體空間。

2.4 完美二叉樹 Perfect Binary Tree

定義：所有層的所有節點都必須是滿的。

完美二叉樹比完全二叉樹的定義更加嚴格，包括最後一層，每一層的節點都要是滿的，畢竟是追求完美的嘛。

所以我們如果知道了層數，就知道了它有多少個節點，也就是一個等比數列求和。

2.5 完滿二叉樹 Full Tree

定義：對於這棵樹的每個節點而言，要麼有 0 個孩子，要麼有 2 個孩子。

大家不要輕視這些概念哦，很多演算法題都會直接考察，在本節的思維導圖裡也附帶了 Leetcode 對應的題目，電面時很喜歡考哦～

3. 高度和深度

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

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

高度是從當前節點到葉子 🍃 節點的；
深度是從當前節點到根 🌲 節點的。

高度 Height

定義：從該節點，到以該節點為根節點的這棵樹的最遠的葉子結點的最長距離。

核心是，從該節點到最遠葉子節點，有幾條邊。

這個概念在分析時空複雜度時非常常用，比如在樹上做一個遞歸複雜度是 O(height)。

為什麼呢？

因為這個距離決定了在 call stack 上有多少層。

深度 Depth

定義：從這個節點到根節點的距離。

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

看樹的角度

俗話說，橫看成嶺側成峰，這句話用在這裡太合適不過了。

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

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

先來總圖：

嶺

最基本的三種遍歷就是

前序 pre order
中序 in order
後序 post order

其實這三種遍歷方式本質都是一樣的，只是輸出/列印節點的順序不同罷了。

來看偽程式碼吧：

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);
}

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

這三種遍歷都是深度優先遍歷 DFS，而層序遍歷是廣度優先遍歷 BFS。

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

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

輸出 5 7 3 1 4.

參考 Leetcode 102 題。

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

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

輸出的就是 5 3 7 1 4.

參考 Leetcode 103 題。

峰

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

比如對於這棵樹，

左視圖 left view：

就是從左邊看的每層的第一個節點。
[5, 7, 9]

右視圖 right view：

就是從右邊看的每層的第一個節點。
[5, 3, 8]

這兩個應該比較簡單，在層序遍歷的時候保留我們需要的值就可以了。

當然還有其他方法，比如前序遍歷可以做左視圖，但不是那麼的直觀，因為你還要判斷這個元素是否是當前層的第一個。大家有想法的可以在群里交流喲。（提示：可以再加一個變數

俯視圖

這個視圖比前兩個稍微難一點，在北美面試中是很愛考的。

首先這個圖中有一個變數叫 column，根節點為 0，左孩子 – 1，右孩子 + 1。

俯視圖指的是，從上往下看這棵樹，把 column 相同的這些節點放在一個 list 里，從上往下放，然後按照 column 從小到大的順序排出來。

所以對於這棵樹，它的俯視圖是：

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

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

Border View

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

就是求這棵樹的「輪廓」。

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

5, 7, 9, 8, 3

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

普通的思路可以用

左視圖 + 葉子結點 + 反著的右視圖

來做，表面上來看需要做三遍遍歷，但是其實一遍遍歷就夠了，因為我剛才說過，DFS 遍歷時，哪種遍歷方式都是一樣的，只是在不同時間列印不同節點罷了。

好了，以上就是本文的全部內容，如果喜歡，記得點贊哦～

8 月雲自習打卡活動正在火熱 🔥 進行中，喏 👇，每天大家都在學習打卡，具體的規則點這裡查看，歡迎你的加入。

我是小齊，終身學習者，每晚 9 點，自習室里我們不見不散 ❤️

Tags: 演算法和數據結構

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

簡介

金融里的二叉樹