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 点，云自习室里不见不散！
