二叉树的遍历与构造

参考LeetCode上(106. 从中序与后序遍历序列构造二叉树)的官方题解.

如何遍历树

遍历树有两种通用策略：

• 深度优先遍历（DFS）

  这种方法以深度 depth 优先为策略，从根节点开始遍历直到某个叶子节点为止，然后回到根节点，再遍历另外一个分支。
  根据根节点，左子节点和右子节点的访问顺序又可以将 DFS 细分为先序遍历 preorder，中序遍历 inorder 和后序遍历 postorder。

• 广度优先遍历（BFS）

  按照高度顺序，从上往下逐层遍历节点;
  先遍历上层节点再遍历下层节点。

下图中按照不同的方法遍历对应子树，得到的序列都是 1-2-3-4-5。根据不同子树结构比较不同遍历方法的特点。

根据两种遍历序列构造树

中序和先序; 中序和后序

这类问题在 Facebook 的面试中常常出现，它可以在$O(N)$O(N)的时间内解决：

• 通常从先序序列或者后序序列开始，根据不同遍历方法的规律，选择合适的节点构造树。
  例如：先序序列的 第一个 节点是根节点，然后是它的左孩子，右孩子等等。
  后序序列的 最后一个 节点是根节点，然后是它的右孩子，左孩子等等。

• 从先序/后序序列中找到根节点，根据根节点将中序序列分为左子树和右子树。从中序序列中获得的信息是：如果当前子树为空（返回None），否则继续构造子树。