关于java:看了齐姐这篇文章再也不怕面试问树了

微信搜寻????「码农田小齐」，关注这个在纽约的程序媛，回复「01-05」能够获取计算机精选书籍、集体刷题笔记、大厂面经、面试材料等资源，么么哒～

在写完了所有线性数据结构之后，明天开启非线性数据结构系列。

咱们明天先来看，什么是“树”。

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

一是因为树的构造人造决定了它和递归分割严密，很多树相干的算法题都非常适合用递归来解；

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

本文先来讲树的根底内容，分为以下大节，每个大节结尾都会有思维导图和对应的 Leetcode 算法题哟～

1. 简介
2. 金融里的二叉树
3. 树的所有概念
   a. 树的 三大特点
   b. 树的 五大种类
   c. 高度和深度
4. 看树的角度
   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. 三大特点

树的三大特点是：

1. 如果把树看成一个无向图，那么它是一个 连通图 connected graph.
2. 树是一个 无环图。
3. 树的节点个数和边的个数之间的关系是固定的。如果树上有 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 遍历时，哪种遍历形式都是一样的，只是在不同工夫打印不同节点罢了。

好了，以上就是本文的全部内容，如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！

我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！

更多干货文章见我的 Github: https://github.com/xiaoqi6666…