【算法】递归+深搜：106.从中序与后序遍历序列构造二叉树（medium）
目录
1、题目链接
相似题目：
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填充hash
for (int i = 0; i < inorder.size(); i++)
{
hash[inorder[i]] = i;
}
return dfs(postorder, inorder.size() - 1, 0, inorder.size() - 1);
}
};原文地址：https://blog.csdn.net/m0_73726899/article/details/143529353
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！