树是由顶点和边组成的且不存在环的数据结构。作为一个应用非常广的数据结构，不仅在工作中常用，在面试中也非常常考。
一是因为树的结构天然决定了它和递归联系紧密，很多树相关的算法题都非常适合用递归来解；
二是因为它的难度介于链表和图之间，非常适合在 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]S=e−rt[pSu+(1−p)Sd]
这就是最简单的二叉树定价模型。
那我们言归正传。
树的所有概念
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 对应的题目，电面时很喜欢考哦～
