889. Construct Binary Tree from Preorder and Postorder Traversal

LeetCode
,

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

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

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

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

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

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

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
	return constructFromPrePost(pre, post, 0, pre.size() -1, 0 ,post.size() - 1);
}
TreeNode* constructFromPrePost(vector<int> &pre, vector<int> &post, 
	int preFirst, int preLast, int postFirst, int postLast) {

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

	int leftPostLast = postFirst;
	while (leftPostLast <= postLast && post[leftPostLast] != pre[preFirst])
	{
		leftPostLast++;
	}
	int leftPreLast = leftPostLast - postFirst + preFirst;

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