看了齐姐这篇文章，再也不怕面试问树了

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: 算法和数据结构

看了齐姐这篇文章，再也不怕面试问树了

简介

金融里的二叉树