【算法】递归+深搜：106.从中序与后序遍历序列构造二叉树（medium）

目录

1、题目链接

相似题目：

2、题目

3、解法

函数头-----找出重复子问题

函数体---解决子问题

4、代码

---

1、题目链接

106.从中序与后序遍历序列构造二叉树（LeetCode）

相似题目：

105.从前序与中序遍历序列构造二叉树

889.根据前序和后序遍历构造二叉树（LeetCode）

2、题目

3、解法

整体思路可以借鉴这篇文章：【算法】递归+深搜：105.从前序与中序遍历序列构造二叉树-CSDN博客

首先，我们还是先确定，中序和后序对于我们构建二叉树的作用。

中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

后序遍历性质： 节点按照 [ 左子树 | 右子树 | 根节点 ] 排序。

后序找出根节点的值，

中序找出左、右子树。

函数头-----找出重复子问题

重复子问题：前序构建二叉树。（根节点、左子树根节点、右子树根节点）

参数： 后序数组、根节点在前序遍历的索引 root 、子树在中序遍历的左边界 left 、子树在中序遍历的右边界 right 

函数体---解决子问题

1、构建根节点、

2、找出根节点在中序遍历中对应的下标 " i "（利用哈希表进行辅助），划分左、右子树

3、构建左子树（更新参数root、left、right）

4、构建右子树（更新参数root、left、right）

4、代码

class Solution {unordered_map<int, int> hash;public:TreeNode* dfs(const vector<int>& postorder, int root, int left, int right){if (left > right)return NULL;TreeNode* node = new TreeNode(postorder[root]);//构建根节点int inorder_root = hash[postorder[root]];     //确定inorder中root的下标int right_size = right - inorder_root;node->left = dfs(postorder, root - 1 - right_size, left, inorder_root - 1);node->right = dfs(postorder, root - 1, inorder_root + 1, right);return node;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//inorder填充hashfor (int i = 0; i < inorder.size(); i++){hash[inorder[i]] = i;}return dfs(postorder, inorder.size() - 1, 0, inorder.size() - 1);}};