面试常考的树，我这样讲给你听！

╰+攻爆jí腚メ 2022-12-01 05:11 155阅读 0赞

![format_png][]

我的新课《C2C 电商系统微服务架构120天实战训练营》在公众号**儒猿技术窝**上线了，感兴趣的同学，可以长按扫描下方二维码了解课程详情：

**课程大纲请参见文末**

![format_png 1][]

![format_png 2][]

--------------------

文章转自：码农田小齐

我们今天先来看，什么是“树”。

树是由顶点和边组成的且不存在环的数据结构。**作为一个应用非常广的数据结构，不仅在工作中常用，在面试中也非常常考。**

一是因为树的结构天然决定了它和递归联系紧密，很多树相关的算法题都非常适合用递归来解；

二是因为它的难度介于链表和图之间，非常适合在 45 分钟的面试里进行考察，所以一场面试中遇到两三轮问树都是再正常不过的了。

本文先来讲树的基础内容，分为以下小节，每个小节开头都会有思维导图和对应的 `Leetcode`算法题哟～

1.  简介
2.  金融里的二叉树
3.  树的所有概念  
    a. 树的**三大特点**  
    b. 树的**五大品种**  
    c. 高度和深度
4.  看树的角度  
    a. 三种 `DFS` 遍历方式  
    b. 两种 `BFS` 遍历方式  
    c. 四种视图

## 简介 ##

其实数据结构里的“树”和我们现实世界里的树挺像的，只不过倒过来了嘛，根朝上。

比如：

![format_png 3][]

在这片森林里，最常用的还是「二叉树」

二叉树，是由很多个 `TreeNode` 构成的这种树形的数据结构，

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

就像链表中的 `ListNode`。

二叉树并不一定非得是“二叉”的，而是说每个节点**最多**有两个孩子，叫 `left` 和 `right`，但也可以没有。

当每个节点都只有一个孩子的时候，就退化成了链表。

所以**链表就是一棵特殊的树，而树是一个特殊的图。**

## 金融里的二叉树 ##

在金融工程里，二叉树是用来在风险中性世界里给期权定价使用的模型。

比如这是一个股价二叉树，其实就是我们把二叉树放倒了看嘛。

![format_png 4][]

有些小伙伴会发现，这里的节点好像少了很多，没错，因为我们让股价每次上涨和下跌的幅度保持不变，所以到第 n 层最多有 n 个节点，而不会像普通的二叉树一样按照等比序列增长。

上图是两期的二叉树，那么最简单的一期的二叉树定价模型表示为：

![format_png 5][]

我们假设当前股票的价格为 `S`，那我们想知道未来某个时刻比如 `t 时刻`的价格，股价有可能上涨也有可能下跌，还可能不变呢。

在该模型里我们就抽象成两种可能性，一种是上涨，一种是下跌，所以可以用二叉树来表示。

假设股票价格会有 `p` 的概率上涨至 `uS`,  
有 `1-p` 的概率下跌至 `dS`.

这里的 `p` 并不是在真实世界里股票上涨的概率，而是一个在风险中性世界里的上涨概率，所以

**股票现在的价格就是未来某时刻的无风险收益的折现**，

即：

这就是最简单的二叉树定价模型。

那我们言归正传。

## 树的所有概念 ##

![format_png 6][]

### 1. 三大特点 ###

树的三大特点是：

1.  如果把树看成一个无向图，那么它是一个**连通图** `connected graph`.
2.  树是一个**无环图**。
3.  树的节点个数和边的个数之间的关系是固定的。如果树上有 `n` 个 `node`，那么它有 `n-1`条边。因为除了根节点，其他的节点都会有一条边指向它。

### 2. 树的品种 ###

**2.1 平衡二叉树** `Balanced Binary Tree`：

*  定义：对于这棵树里的**每个节点**，它的左子树和右子树的高度差不大于 1。

这里要注意，是对于**每个节点**，而不只是对于根结点。

比如左边这棵树就不是平衡二叉树，右边的才是。

![format_png 7][]

那么大名鼎鼎的 `AVL-Tree` 就是平衡二叉树，准确说是自平衡二叉查找树。

那什么是二叉查找树呢？

**2.2 二叉查找树** `Binary Search Tree`

*  定义：对于这棵树里的每个节点，
 *   *  它左子树里的每个节点的值都小于它的值；
     *  它右子树里的每个节点的值都大于它的值。

![format_png 8][]

对二叉查找树，最重要的性质就是：

**在做中序遍历时，这个序列是一个升序序列。**

当你在做二叉查找树的算法题没有思路时，可以想想这个性质，很多题目都会迎刃而解。

**2.3 完全二叉树** `Complete Binary Tree`：

*  定义：除了最后一层，其他层都是满的，那么最后一层的节点要靠左排列且中间不允许有气泡。

比如左边不是完全二叉树，右边的是。

![format_png 9][]

那么完全二叉树的最大的好处就是因为它排列紧密没有气泡，所以可以用数组来存储，这样就大大节省了内存空间。

**2.4 完美二叉树** `Perfect Binary Tree`

*  定义：所有层的所有节点都必须是满的。

完美二叉树比完全二叉树的定义更加严格，包括最后一层，每一层的节点都要是满的，毕竟是追求完美的嘛。

所以我们如果知道了层数，就知道了它有多少个节点，也就是一个等比数列求和。

![format_png 10][]

**2.5 完满二叉树** `Full Tree`

*  定义：对于这棵树的每个节点而言，要么有 0 个孩子，要么有 2 个孩子。

![format_png 11][]

### 3. 高度和深度 ###

树的高度 `height` 和深度 `depth` 是两个非常重要的概念，比如 Leetcode 104 和 111 就是专门求树的高度的。

而这两个概念是相反方向的，大体上呢，

*  **高度是从当前节点到叶子 ???? 节点的；**
 *  **深度是从当前节点到根 ???? 节点的。**

![format_png 12][]

**高度** `Height`

*  定义：从该节点，到以该节点为根节点的这棵树的最远的叶子结点的最长距离。

核心是，从该节点到最远叶子节点，有几条边。

这个概念在分析时空复杂度时非常常用，比如在树上做一个递归复杂度是 O(height)。

为什么呢？

因为这个距离决定了在 `call stack` 上有多少层。

**深度** `Depth`

*  定义：从这个节点到根节点的距离。

这个概念用的比较少，是和高度方向相反的概念。

## 看树的角度 ##

俗话说，横看成岭侧成峰，这句话用在这里太合适不过了。

对于树的几种遍历方式想必大家都不陌生，这就是我所说的「岭」；

而还有一种面试常考题是问 `left/right/vertical/border view`，也就是求树的左视图、右视图、俯视图、border view 这我没找到中文翻译。。这就是我所说的「峰」。

先来总图：

![format_png 13][]

### 岭 ###

最基本的三种遍历就是

*  前序 `pre order`
 *  中序 `in order`
 *  后序 `post order`

其实这三种遍历方式本质都是一样的，只是输出/打印节点的顺序不同罢了。

![format_png 14][]

来看伪代码吧：

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`。

![format_png 15][]

输出 `5 7 3 1 4`.

参考 Leetcode 102 题。

也就是每一层按照从左到右的顺序遍历。

那么还有一种 `Zigzag` 的遍历方式，就是**一行从左到右，下一行从右到左**这样子。

![format_png 16][]

输出的就是 `5 3 7 1 4`.

参考 Leetcode 103 题。

### 峰 ###

`left/right/vertical/border view`，也就是求树的左视图、右视图、俯视图，是非常爱考的一类题，它们是什么意思呢？

比如对于这棵树，

![format_png 17][]

**左视图** `left view`：

*  就是从左边看的每层的第一个节点。
 *  `[5, 7, 9]`

**右视图** `right view`：

*  就是从右边看的每层的第一个节点。
 *  `[5, 3, 8]`

这两个应该比较简单，在层序遍历的时候保留我们需要的值就可以了。

当然还有其他方法，比如前序遍历可以做左视图，但不是那么的直观，因为你还要判断这个元素是否是当前层的第一个。大家有想法的可以在群里交流哟。（提示：可以再加一个变量

**俯视图**

这个视图比前两个稍微难一点，在北美面试中是很爱考的。

首先这个图中有一个变量叫 `column`，根节点为 0，左孩子 - 1，右孩子 + 1。

俯视图指的是，从上往下看这棵树，把 column 相同的这些节点放在一个 list 里，从上往下放，然后按照 column 从小到大的顺序排出来。

![format_png 18][]

所以对于这棵树，它的俯视图是：

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

这题就作为本文的思考题啦，不是很难，大家可以在评论区或者群里交流～

**Border View**

在讲完前三种视图之后，这个 `border view` 想必大家都能猜出来意思了。

就是求这棵树的“轮廓”。

![format_png 19][]

比如还是这棵树，它的 `border view` 就是：

`5, 7, 9, 8, 3`

这题的大体思路不难，但是细节很多，而且很多条件可能就像我给的这样并没有定义清楚，所以你需要和面试官不断的 `clarify` 很多细节。

普通的思路可以用

**左视图 + 叶子结点 + 反着的右视图**

来做，表面上来看需要做三遍遍历，但是其实一遍遍历就够了，因为我刚才说过，DFS 遍历时，哪种遍历方式都是一样的，只是在不同时间打印不同节点罢了。

**END**

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

[format_png]: /images/20221123/a71d8175532e46c6a2e44b98c9b72722.png
[format_png 1]: /images/20221123/5e5c07853e2e4e0b8eb161e265b9ce01.png
[format_png 2]: /images/20221123/11696e288ca44de1b1f1124075e314bf.png
[format_png 3]: /images/20221123/a76808ecd93944809f6dec3599878612.png
[format_png 4]: /images/20221123/4398989526664a1796fc30fee0ceff7b.png
[format_png 5]: /images/20221123/5d637728ab7c49ea880a3fbade3109f0.png
[format_png 6]: /images/20221123/c2ba28b07bfa402693398e6ef2d24c56.png
[format_png 7]: /images/20221123/92b550a82c9040d284534c25c5ba2c35.png
[format_png 8]: /images/20221123/01f8422c793547aea393200911166a2e.png
[format_png 9]: /images/20221123/420833d455aa4177b20a4be84796c409.png
[format_png 10]: /images/20221123/144122687df4435ea13a8c9d2fac6fce.png
[format_png 11]: /images/20221123/1919ac282b514b3cb2d26505a8fdadb3.png
[format_png 12]: /images/20221123/9941fc8f4cd14acdb409af911bad1c0f.png
[format_png 13]: /images/20221123/dc245547c90846478d759678fb7b350b.png
[format_png 14]: /images/20221123/c7f62b37077340e1bf6240cab78425d2.png
[format_png 15]: /images/20221123/34f5ac06752a4ae3a4c64527705e89a1.png
[format_png 16]: /images/20221123/95978e4467ea4666975542025a4bdd88.png
[format_png 17]: /images/20221123/0b97a1b262c741a0922294f03be2b7df.png
[format_png 18]: /images/20221123/721c77f40f4d432ba410cccdccbd6165.png
[format_png 19]: /images/20221123/c6a2ecf54d3f4d8a92660b9af6bec1c2.png
[format_png 20]: /images/20221123/bac19a2caa1943e59a0364811c3e9d91.png
[format_png 21]: /images/20221123/c74bc39dba474b0d92d124a4058f6a09.png
[format_png 22]: /images/20221123/610c3006171b42e884be7dac64539868.png
[format_png 23]: /images/20221123/e344a73691c14f69a4dec80b9c1ce2e6.png