OJ-leetcode-106. 从中序与后序遍历序列构造二叉树（递归、二叉树）

ゞ浴缸里的玫瑰 2022-12-10 08:55 107阅读 0赞

**目录**

题目

思路

代码

结果

优秀题解

提升笔记

全部代码

相关题目

--------------------

# 题目 #

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:  
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = \[9,3,15,20,7\]  
后序遍历 postorder = \[9,15,7,20,3\]

返回如下的二叉树：

3  
   / \\  
  9  20  
    /  \\  
   15   7  
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

# 思路 #

首先，使用算法递归解题，是自底向上，不需要记忆化的递归。接下来想到的是由中序和后序得到先序。但是发现先序并没有能加快解题速度，就否了。

然后我就想记录位置标记，标记根节点在中序序列中的下标，还有左右子树的下标。比如，中序序列根的下标是i，标记为\[0,i-1,i,i+1,maxlen-1\]，后序序列根的下标为j,标记为\[0,i-1,i,j-1,j\]。不过，我看给的函数只有两个参数，没有办法传更多参数 ，就想另外保存下来吧。看了其他人的题解才发现，可以不只写一个函数，可以再写另一个函数，在给定的函数中调用即可，之前一直以为最多只能是改改给定函数的参数名，才知道可以再写函数。

## 代码 ##

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    		if (inorder.size() == 0)return NULL;
    		TreeNode*  r = new TreeNode(postorder.back());
    		if (postorder.size() == 1)
    		{
    			r->left = NULL;
    			r->right = NULL;
    			return r;
    		}
    		int i = 0;
    		vector<int> l_in;
    		vector<int> r_in;
    		int in_len = inorder.size();
    		// 左子树的中序遍历 找到根
    		while (inorder[i] != r->val)
    		{
    			l_in.emplace_back(inorder[i]);
    			i++;
    		}
    		i++; //跳过根节点
    		//右子树的中序遍历
    		while (i <= in_len - 1) {
    				r_in.emplace_back(inorder[i]);
    				i++;
    		}
    		int j = 0;
    		vector<int> l_post;
    		vector<int> r_post;
    		int post_len = postorder.size();
    		// 左子树的后序遍历
    		int l_len = l_in.size();
    		int k = 0;
    		while (k < l_len)
    		{
    			l_post.emplace_back(postorder[j]);
    			j++;
    			k++;
    		}
    		//右子树的后序遍历
    		while (j < post_len-1)
    		{
    			r_post.emplace_back(postorder[j]);
    			j++;
    		}
    		//递归生成左右子树
    		r->left = buildTree(l_in,l_post);
    		r->right = buildTree(r_in,r_post);
    		return r;
    	}

记得边界条件，空树。

优化就是使用了emplace\_back、size()函数写在for循环外面、加了一个为size为1时的停止条件，少递归一层。

## 结果 ##

![20200925105931276.PNG][] 递归过程

# 优秀题解 #

[https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/di-gui-jian-shu-jiang-jie-de-hen-xiang-xi-by-lllll/][https_leetcode-cn.com_problems_construct-binary-tree-from-inorder-and-postorder-traversal_solution_di-gui-jian-shu-jiang-jie-de-hen-xiang-xi-by-lllll]

# 提升笔记 #

1.  leetcode中可以再写函数
2.  unordermap做哈希表

# 全部代码 #

/*
    Project: 106. 从中序与后序遍历序列构造二叉树
    Date:    2020 / 09 / 25
    Author:  Frank Yu
    * /
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    #include<vector>
    #include<iostream>
    #include<unordered_map>
    using namespace std;
    
    struct TreeNode {
    	int val;
    	TreeNode *left;
    	TreeNode *right;
    	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution {
    	unordered_map<int, int> index;
    public:
    	// 优化
    	TreeNode* myBuildTree(vector<int>& postorder, vector<int>& inorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
    		// 空树
    		if (postorder_left > postorder_right) return NULL;
    		// 后序中序下标
    		int postorder_root = postorder_right;
    		int inorder_root = index[postorder[postorder_root]];
    		// 建立根节点
    		TreeNode* root = new TreeNode(postorder[postorder_root]);
    		//子树大小
    		int size_left_subtree = inorder_root - inorder_left;
    		//递归建树
    		root->left = myBuildTree(postorder, inorder, postorder_left,
    			postorder_left + size_left_subtree - 1, inorder_left, inorder_root - 1);
    		root->right = myBuildTree(postorder, inorder, postorder_left + size_left_subtree,
    			postorder_right - 1, inorder_root + 1, inorder_right);
    		return root;
    	}
    	// 思路1
    	//TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    	//	if (inorder.size() == 0)return NULL;
    	//	TreeNode*  r = new TreeNode(postorder.back());
    	//	cout <<"根:"<<r->val << endl;
    	//	if (postorder.size() == 1)
    	//	{
    	//		r->left = NULL;
    	//		r->right = NULL;
    	//		return r;
    	//	}
    	//	int i = 0;
    	//	vector<int> l_in;
    	//	vector<int> r_in;
    	//	int in_len = inorder.size();
    	//	// 左子树的中序遍历 找到根
    	//	while (inorder[i] != r->val)
    	//	{
    	//		l_in.emplace_back(inorder[i]);
    	//		i++;
    	//	}
    	//	i++; //跳过根节点
    	//	//右子树的中序遍历
    	//	while (i <= in_len - 1) {
    	//			r_in.emplace_back(inorder[i]);
    	//			i++;
    	//	}
    	//	int j = 0;
    	//	vector<int> l_post;
    	//	vector<int> r_post;
    	//	int post_len = postorder.size();
    	//	// 左子树的后序遍历
    	//	int l_len = l_in.size();
    	//	int k = 0;
    	//	while (k < l_len)
    	//	{
    	//		l_post.emplace_back(postorder[j]);
    	//		j++;
    	//		k++;
    	//	}
    	//	//右子树的后序遍历
    	//	while (j < post_len-1)
    	//	{
    	//		r_post.emplace_back(postorder[j]);
    	//		j++;
    	//	}
    	//	//递归生成左右子树
    	//	//左子树中序遍历
    	//	cout << "左子树:";
    	//	for (auto i : l_in)
    	//	{
    	//		cout << i;
    	//	}
    	//	cout << " ";
    	//	//左子树后序遍历
    	//	for (auto i : l_post)
    	//	{
    	//		cout << i;
    	//	}
    	//	cout << endl;
    	//	cout << "右子树:";
    	//	//右子树中序遍历
    	//	for (auto i : r_in)
    	//	{
    	//		cout << i;
    	//	}
    	//	cout << " ";
    	//	//右子树后序遍历
    	//	for (auto i : r_post)
    	//	{
    	//		cout << i;
    	//	}
    	//	cout << endl;
    	//	r->left = buildTree(l_in,l_post);
    	//	r->right = buildTree(r_in,r_post);
    	//	return r;
    	//}
    	// 优化
    	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    		int n = postorder.size();
    		for (int i = 0; i < n; i++) {
    			index[inorder[i]] = i;
    		}
    		return myBuildTree(postorder, inorder, 0, n - 1, 0, n - 1);
    	}
    };
    void PreOrder(TreeNode* T)
    {
    	if (T != NULL)
    	{
    		printf("%d ", T->val);
    		PreOrder(T->left);//递归先序遍历左右子树
    		PreOrder(T->right);
    	}
    }
    //主函数
    int main()
    {
    	vector<int> inorder { 9,3,15,20,7 };
    	vector<int> postorder { 9,15,7,20,3 };
    	Solution s;
    	TreeNode* T = s.buildTree(inorder,postorder);
    	PreOrder(T);
    	cout << endl;
    	return 0;
    }

# 相关题目 #

[LeetCode889 根据前序和后序遍历构造二叉树][LeetCode889]  
[LeetCode105 从前序与中序遍历序列构造二叉树][LeetCode105]

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[20200925105931276.PNG]: /images/20221123/254f6d3bb24a4b19918d1102c4f9c353.png
[https_leetcode-cn.com_problems_construct-binary-tree-from-inorder-and-postorder-traversal_solution_di-gui-jian-shu-jiang-jie-de-hen-xiang-xi-by-lllll]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/di-gui-jian-shu-jiang-jie-de-hen-xiang-xi-by-lllll/
[LeetCode889]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
[LeetCode105]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799