6.树

树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。

正因为树有这样的性质，大部分关于树的面试题都与递归有关，换句话说，面试官希望通过一道关于树的问题来考察你对于递归算法掌握的熟练程度。

树的形状

在面试中常考的树的形状有：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。

对于一些特殊的树，例如红黑树（Red-Black Tree）、自平衡二叉搜索树（AVL Tree），一般在面试中不会被问到，除非你所涉及的研究领域跟它们相关或者你十分感兴趣，否则不需要特别着重准备。

关于树的考题，无非就是要考查树的遍历以及序列化（serialization)。

方法：先访问根节点，然后访问左子树，最后访问右子树。在访问左、右子树的时候，同样，先访问子树的根节点，再访问子树根节点的左子树和右子树，这是一个不断递归的过程。

应用场景：运用最多的场合包括在树里进行搜索以及创建一棵新的树。

方法：先访问左子树，然后访问根节点，最后访问右子树，在访问左、右子树的时候，同样，先访问子树的左边，再访问子树的根节点，最后再访问子树的右边。

应用场景：最常见的是二叉搜索树，由于二叉搜索树的性质就是左孩子小于根节点，根节点小于右孩子，对二叉搜索树进行中序遍历的时候，被访问到的节点大小是按顺序进行的。

方法：先访问左子树，然后访问右子树，最后访问根节点。

应用场景：在对某个节点进行分析的时候，需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行，好比你在修剪一棵树的叶子，修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。

掌握好这三种遍历的递归写法和非递归写法是非常重要的，懂得分析各种写法的时间复杂度和空间复杂度同样重要。

无论是前端工程师，还是后端工程师，在准备面试的时候，树这个数据结构都是最应该花时间学习的，既能证明你对递归有很好的认识，又能帮助你学习图论（关于图论，我们将在下一节课一起讨论）。树的许多性质都是面试的热门考点，尤其是二叉搜索树（BST）。