从前序遍历结果中重建二叉搜索树

今天遇到一个有趣的问题：已知有一个无重复元素的二叉搜索树的前序遍历结果，要求重建该二叉搜索树。

回顾

首先回顾一下前序遍历和二叉搜索树的概念。

前序遍历

二叉树的前序遍历指得是：对于任意的节点及其左右子节点，在遍历结果中出现的顺序总是「父节点 -> 左子树（如果有） -> 右子树（如果有）」；由于二叉树的自相似结构，这种描述唯一确定的遍历顺序即是前序遍历。

二叉搜索树

二叉搜索树是一种特殊的二叉树，它要求：对于任意的节点及其左右子节点作为根节点形成的左右子树，满足：左子树的所有节点的值小于父节点的值，右子树的所有节点的值大于父节点的值。

显然，二叉搜索树的中序遍历是从小到大排序的。

分析

唯一性

首先要考虑，一个无重复元素的二叉搜索树的前序遍历结果能否唯一确定一个二叉搜索树？答案是可以的，简要证明如下：

已知二叉搜索树的前序遍历结果，即知晓二叉搜索树中所有元素；
对二叉搜索树中所有元素进行从小到大排序，根据二叉搜索树的性质，即得到该二叉搜索树的中序遍历结果；
已知二叉树的前序遍历结果和中序遍历结果，可以唯一地确定一个二叉树，即该二叉搜索树。

由此可知，一个无重复元素的二叉搜索树的前序遍历结果，确实能够唯一地确定一个二叉搜索树。

时间复杂度

重建二叉搜索树必然要获知该二叉搜索树中的全部结果。因此，时间复杂度必然不小于 $O(n)$ ，由此我们得到一个下界。

又从上述唯一性证明的过程中可知一种重建方法，分析该方法的复杂度可得到一个上界。现在我们简单分析一下该方法的时间复杂度。

一种恢复二叉搜索树的方法：

对结果进行从小到大排序，得到中序遍历结果。

根据前序遍历结果和中序遍历结果，重建二叉树。

该方法的时间复杂度是两步之和，其中第 (1) 步的时间复杂度为 $O(n\log(n))$ ；关键要求得第 (2) 步的时间复杂度。

根据前序遍历结果和中序遍历结果，重建二叉树的方法：

根据前序遍历结果，确定树根

根据中序遍历结果，确定树根位置

根据中序遍历结果，确定左子树（如果有）元素数量

根据 (3) 的结果，在前序遍历结果中，确定左右子树（如果有）的树根位置

如此分治递归

若使用支持随机访问的数组存储前序、中序遍历结果，这里的 (1), (3), (4) 步的复杂度均是常数 $O(1)$ 。对于 (2)，若中序遍历是有序结果（二叉搜索树的情况），可用二分搜索确定树根位置，这一步的复杂度是 $O(\log(n))$ ，否则只能逐一遍历，复杂度是 $O(n)$ 。根据「主定理」，这种重建二叉树的方法的时间复杂度不超过 $O(n\log(n))$ 。

由此可知，根据前序遍历结果重建二叉搜索树的方法，其时间复杂度下界是 $O(n)$ ，上界是 $O(n\log(n))$ 。

向 $\Theta(n)$ 进发

回顾借助中序遍历结果重建二叉树的步骤，我们发现，中序遍历结果的核心作用是通过确定左子树（如果有）元素的数量，在前序遍历中确定左右子树的根节点。考虑到，在前序遍历中，左子树的根节点的位置是平凡的——如果存在左子树，左子树根节点就是整棵树根节点的在前序遍历中的下一个元素。所以关键是要想办法确定右子树（如果有）根节点的位置。

好消息是，我们现在需要重建的二叉树是二叉搜索树。因此，树根的右孩子，就是前序遍历中第一个比根节点大的那个元素。这样一来，我们就能确定根节点的左右孩子的位置了，如此一来，只需要递归就能解决问题。

于是，遗留的问题变成了：如何在常数时间内找到第一个比根节点大的元素的位置。

讲道理，单就查找元素的问题而言，我们是做不到的。最快的二分的复杂度也有 $\Theta(\log(n))$ ，何况它还有额外要求。但是，我们已知：根节点到根节点右孩子（如果有）之间的所有元素，都是根节点左子树（如果有）的元素（假设其个数是 $k$ ）。如果我们有办法在寻找右孩子的过程中，把左子树构建出来，我们就能把寻找右孩子的复杂度 $\Theta(k)$ 均摊到这 $k$ 个左子树的元素上去，复杂度就变成了常数。要做到这一点，依赖于实现。

递归实现

TreeNode* rebuildBST(const std::vector<int>& preorder,
                                   const int bound = std::numeric_limits<int>::max()) {
  static size_t i = 0;
  if (preorder.size() == i or preorder[i] > bound) { return nullptr; }
  auto node = new TreeNode(preorder[i]);
  ++i;
  node->left = rebuildBST(preorder, node->val);
  node->right = rebuildBST(preorder, bound);
  return node;
}

这里，所有递归调用都共享同一个下标 i，它从 0 开始自增到 preorder.size() 后，所有递归退出。在每次递归调用中，除开构建节点的开销，都只有常数项的操作：至多两次比较，一次变量自增。因此，复杂度是 $\Theta(n)$ 。

非递归实现

再多一点挑战：有没有办法用非递归的方式去实现这一算法呢？

既然会问出来，那答案肯定是「有」。

我们分析一下递归版本的代码。

函数的默认参数 std::numeric_limits<int>::max() 实际上是为了简化代码实现，而引入的「哨兵」。
变量 i 在所有递归调用中共享，从 0 开始自增到 preorder.size() 后，所有递归退出，实际上起到了循环的作用。
每次递归调用中，preorder 是不变的，变化的只有 bound；它保证了在处理右子树之前，先处理完左子树的所有节点。

因此，若要非递归地实现这一算法，我们需要：

用某种方式，重新引入哨兵 std::numeric_limits<int>::max()；
循环，从 0 -> preorder.size()；
提供一个栈，直接或间接地保存这里的 bound。

于是有实现：

TreeNode* rebuildBST(const std::vector<int>& preorder) {
  TreeNode* dummy = new TreeNode(std::numeric_limits<int>::max());
  std::stack<TreeNode*> s;
  s.push(dummy);
  for (int x : preorder) {
    TreeNode* node = new TreeNode(x);
    TreeNode* wk = nullptr;
    for (; s.top()->val < x; wk = s.top(), s.pop()) { ; }
    if (wk == nullptr) {
      s.top()->left = node;
    } else {
      wk->right = node;
    }
    s.push(node);
  }
  TreeNode* res = dummy->left;
  dummy->left = nullptr;
  delete dummy;
  return res;
}

这里，dummy 起到了哨兵的作用；for (:) 是上述提到的循环；for (;;) 里每一次弹栈，都意味着遇到了右孩子，对应递归版本中的 return nullptr;。

从非递归的版本中看时间复杂度是很明显的。for (:) 之外的内容只有常数复杂度，for (:) 循环之内的内容要重点分析 for (;;) 循环。for (;;) 循环每执行一次，都有一次 s.pop() 操作，它与 s.push(node) 一一对应。因此，有多少次 s.push(node) 就有多少次 s.pop()（不算 s.push(dummy)）。于是，均摊到每次 for (:) 循环中去，for (;;) 恰好只执行一次 wk = s.top() 和 s.pop()。于是 for (:) 之内的内容也只有常数复杂度。于是，这个实现的复杂度为 $\Theta(n)$ 。

这里非递归的实现，是从递归实现中变形出来的。但实际上，非递归的实现，也有其自身的含义。

首先看「栈」。由于是「前序遍历」，所以一个节点的祖辈节点一定在父辈节点之前。考虑到任何一个节点，都只和父亲节点直接建立联系，因此从前往后遍历 preorder 时，必然要用到栈结构，保存历代祖先。（捶桌笑）

然后看弹栈的循环。这实际上透露的是一种自底向上的思路：如果我遇到了一个节点，它是某个节点的左孩子，那么一定是刚才入栈的节点；如果它是某个节点的右孩子，这意味着这个节点的左子树都已经处理完了，就要依次弹栈。通过这样的方式，我们能找到每一个「孩子」的「父亲」是谁。与之对应，递归版本的实现，则是一种自顶向下的思路：我现在有一个节点，它的左孩子在哪里，你给我找出来（递归调用），找到之后再继续找它的右孩子（递归调用）。

总结

遇到这个问题，我们的分析从确定唯一性开始。运用二叉搜索树中序遍历元素有序的特点，我们借助「前序中序唯一确定二叉树」的定理，很快确定了唯一性。（这要感谢 @linjie）

顺着唯一性出发，我们马上确定了一种重建二叉树的方法，从而确定了一个时间复杂度上界。

在确定上界之后，我们会希望继续降低算法的时间复杂度。自然而然地，我们从已有的方法出发，寻找可能的改进点。由于我们手头只有前序遍历结果，自然地，我们就会去想中序遍历在已有算法中起到的作用是什么，并寻找其替代。

如此，我们自顶向下地，很容易地找到了上述递归实现。在转递归为非递归的过成功中，我们又发现了自底向上的解法。这促使我们在将来的日子里，在符合常规思维的「自顶向下」中，多去找找「自底向上」的解法，可能会有奇效。