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

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

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

  • 先序:根节点,左子树先序,右子树先序
  • 后序:左子树后序,右子树后序,根节点。

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

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

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

代码如下:

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;
}

作者:wuxiaobai24

发表日期:10/8/2020

本文首发地址:889. Construct Binary Tree from Preorder and Postorder Traversal

版权声明:CC BY NC SA 4.0

本站总访问量次 本站访客数人次

Design by wuxiaobai24. Power by Gatsby.js. The website content is licensed CC BY NC SA 4.0.

You can find the source code in Github.