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

石杉的架构笔记 2020-08-26

1140

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

课程大纲请参见文末

文章转自：码农田小齐

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

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

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

二是因为它的难度介于链表和图之间，非常适合在 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
并不是在真实世界里股票上涨的概率，而是一个在风险中性世界里的上涨概率，所以

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

即：

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

那我们言归正传。

树的所有概念

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 个孩子。

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