Code & Func

今天的题目是889. Construct Binary Tree from Preorder and Postorder Traversal。

和前/后序+中序构造二叉树的方法差不多，毕竟这里只要求输出一个符合的解即可。

首先，我们知道先序遍历和后序遍历得到的输出基本结构如下：

先序：根节点，左子树先序，右子树先序
后序：左子树后序，右子树后序，根节点。

从上面我们可以知道以下两点：

一棵树先序的第一个元素和后序的最后一个元素相等。
左子树/右子树的先序与后序由相同的元素组成。

进而我们可以得出以下推论：先序的第二个元素（如果有的话）是其左子树根节点，即应该等于左子树后序的最后一个元素，我们可以用这个推论来分割左右子树。知道如何分割左右子树了，那么只需要和前/后序+中序构造二叉树一样递归建树即可。

代码如下：

1
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
2
  return constructFromPrePost(pre, post, 0, pre.size() -1, 0 ,post.size() - 1);
3
}
4
TreeNode* constructFromPrePost(vector<int> &pre, vector<int> &post,
5
  int preFirst, int preLast, int postFirst, int postLast) {
6

7
  if (preFirst > preLast || postFirst > postLast) return nullptr;
8

9
  TreeNode *root = new TreeNode(pre[preFirst]);
10
  preFirst++; postLast--;
11
  if (preFirst > preLast || postFirst > postLast) return root;
12

13
  int leftPostLast = postFirst;
14
  while (leftPostLast <= postLast && post[leftPostLast] != pre[preFirst])
15
  {
8 collapsed lines
16
    leftPostLast++;
17
  }
18
  int leftPreLast = leftPostLast - postFirst + preFirst;
19

20
  root->left = constructFromPrePost(pre, post, preFirst, leftPreLast, postFirst, leftPostLast);
21
  root->right = constructFromPrePost(pre, post, leftPreLast + 1, preLast, leftPostLast + 1, postLast);
22
  return root;
23
}