树的编码面试技巧指南

树是一种广泛使用的抽象数据类型，用于表示具有连接节点的层次结构。树中的每个节点可以连接到许多子节点，但必须恰好连接到一个是父节点的节点，除了根节点，它没有父节点。

树是一个无向且连通的无环图。没有循环或环路。每个节点可以像自己的子树中的根节点一样，使得递归成为遍历树的有用技术。

为了面试的目的，你通常会遇到二叉树而不是三元（3个子节点）或N元（N个子节点）树。在本页中，我们将涵盖二叉树和二叉搜索树，后者是二叉树的特例。

树通常用于表示层次数据，例如文件系统、JSON和HTML文档。请查看关于字典树的部分，它是一种用于高效存储和搜索字符串的高级树。

学习资源

视频
树，加州大学圣地亚哥分校
二叉搜索树的简要指南（幻灯片），萨缪尔·阿尔班尼，剑桥大学
红黑树的简要指南（幻灯片），萨缪尔·阿尔班尼，剑桥大学
B树的简要指南（幻灯片），萨缪尔·阿尔班尼，剑桥大学
阅读材料
如何不被树难倒，basecs
让二叉树忙碌起来，basecs
其他（如果你有时间）
小AVL树能做什么，basecs
忙于B树，basecs
用红黑树涂黑节点，basecs

你需要知道的常见术语

邻居 - 节点的父节点或子节点
祖先 - 通过遍历其父链可达的节点
后代 - 在节点的子树中的节点
度 - 节点的子节点数量
树的度 - 树中节点的最大度
距离 - 两个节点之间最短路径上的边数
层级/深度 - 从节点到根节点的唯一路径上的边数
宽度 - 某一层级中的节点数量

二叉树

二进制意味着两个，所以二叉树中的节点最多有两个子节点。

二叉树术语

完全二叉树 - 一个完全二叉树是这样一个二叉树，在该树中，除了可能最后一级之外，每一级都是完全填满的，并且最后一级的所有节点都尽可能靠左排列。
平衡二叉树 - 一个二叉树结构，在该结构中，每个节点的左右子树的高度差不会超过1。

遍历

给定这样的树，这些是对各种遍历的结果。

中序遍历 - 左 -> 根 -> 右
结果：2, 7, 5, 6, 11, 1, 9, 5, 9
前序遍历 - 根 -> 左 -> 右
结果：1, 7, 2, 6, 5, 11, 9, 9, 5
后序遍历 - 左 -> 右 -> 根
结果：2, 5, 11, 6, 7, 5, 9, 9, 1

请注意，二叉树的中序遍历不足以唯一地序列化树。前序或后序遍历也是必需的。

二叉搜索树（BST）

BST的中序遍历将给你所有按顺序排列的元素。

非常熟悉BST的属性，并验证一个二叉树是否为BST。这种情况比预期出现的要多。

当问题涉及到BST时，面试官通常在寻找运行速度比O(n)更快的解决方案。

时间复杂度

操作	大O表示
访问	O(log(n))
搜索	O(log(n))
插入	O(log(n))
删除	O(log(n))

平衡树的遍历空间复杂度为O(h)，其中h是树的高度，而遍历非常倾斜的树（基本上是一个链表）将是O(n)。

面试时需要注意的事项

你应该非常熟悉递归编写前序、中序和后序遍历。作为扩展，尝试迭代编写它们。有时面试官会要求候选人使用迭代方法，特别是如果候选人写完递归方法太快的话。

边缘情况

空树
单节点
两个节点
非常倾斜的树（如链表）

常见程序

熟悉以下程序，因为许多树问题在解决方案中使用了这些程序中的一个或多个：

插入值
删除值
计算树中节点的数量
判断值是否在树中
计算树的高度
二叉搜索树确定它是否是二叉搜索树获取最大值获取最小值

技巧

使用递归

递归是遍历树的最常见方法。当你注意到子树问题可以用来解决整个问题时，尝试使用递归。

在使用递归时，请始终记住检查基本情况，通常在节点为 null 时。

有时你的递归函数可能需要返回两个值。

按层级遍历

当被要求按层级遍历树时，使用广度优先搜索。

节点的总和

如果问题涉及沿路节点的总和，请确保检查节点是否可以是负数。

基本问题

如果你正在为这个主题学习，这是练习的基本问题。