前言：
此刻我们对“先序中序遍历构造二叉树”大约比较重视，你们都想要分析一些“先序中序遍历构造二叉树”的相关资讯。那么小编也在网络上汇集了一些对于“先序中序遍历构造二叉树””的相关内容，希望朋友们能喜欢，看官们一起来了解一下吧！题目描述
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例
输入：
中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]
输出：
3 / \ 9 20 / \ 15 7写在前面
本文答案参考自 LeetCode 官方题解。[敲打]
这道题也有点看不懂。 (⊙﹏⊙)
解法1：递归
（以下出自LeetCode官方）
中序遍历的形式是：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
后序遍历的形式是：[ [左子树的前序遍历结果], [右子树的前序遍历结果] , 根节点]
我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。
代码
int post_idx;unordered_map<int, int> idx_map;TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){ // 如果这里没有节点构造二叉树了，就结束 if (in_left > in_right) { return nullptr; } // 选择 post_idx 位置的元素作为当前子树根节点 int root_val = postorder[post_idx]; TreeNode* root = new TreeNode(root_val); // 根据 root 所在位置分成左右两棵子树 int index = idx_map[root_val]; // 下标减一 post_idx--; // 构造右子树 root->right = helper(index + 1, in_right, inorder, postorder); // 构造左子树 root->left = helper(in_left, index - 1, inorder, postorder); return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {// 从后序遍历的最后一个元素开始post_idx = (int)postorder.size() - 1;// 建立（元素，下标）键值对的哈希表int idx = 0;for (auto& val : inorder) { idx_map[val] = idx++;}return helper(0, (int)inorder.size() - 1, inorder, postorder);}作者：LeetCode-Solution链接：来源：力扣（LeetCode）解法2：迭代我还是看不懂[大哭][大哭][大哭]
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #先序中序遍历构造二叉树 #先序中序后序遍历二叉树
