网站备案信息传网站开发技术方法与路线
目录
1、题目链接
2、题目介绍
3、解法
函数头-----找出重复子问题
函数体---解决子问题
4、代码
1、题目链接
105.从前序与中序遍历序列构造二叉树. - 力扣（LeetCode）
2、题目介绍
3、解法
前序遍历性质： 节点按照
[ 根节点 | 左子树 | 右子树 ]排序。
中序遍历性质： 节点按照[ 左子树 | 根节点 | 右子树 ]排序。
因此，我们可以利用前序确定二叉树的根节点，中序遍历确定左、右子树的结点数。
- 前序遍历的首元素 为 树的根节点 node 的值。
- 在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。
- 根据中序遍历中的左（右）子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。
函数头-----找出重复子问题
重复子问题：前序构建二叉树。（根节点、左子树根节点、右子树根节点）
参数： 根节点在前序遍历的索引
root、子树在中序遍历的左边界left、子树在中序遍历的右边界right函数体---解决子问题
1、构建根节点、
2、找出根节点在中序遍历中对应的下标 " i "（利用哈希表进行辅助），划分左、右子树
3、构建左子树（更新参数root、left、right）
4、构建右子树（更新参数root、left、right）
4、代码
class Solution {public:unordered_map<int, int> hash; //哈希表，便于寻找inorder中根节点的下标//参数: 前序，根节点对应的在前序的下标，左子树起始位置(中序)，右子树结束位置（中序）TreeNode* dfs(const vector<int>& preorder, int root, int left, int right) {if (left > right)//左右子树都为空{return NULL;}//构建根节点TreeNode* BTroot = new TreeNode(preorder[root]);int inorder_root = hash[preorder[root]]; //根节点对应的在中序的下标//构建左右子树BTroot->left = dfs(preorder, root + 1, left, inorder_root - 1);//右子树的根节点下标（前序）= root +left_Tree_size +1 ( inorder_root - left + root +1)BTroot->right = dfs(preorder, inorder_root - left + root + 1, inorder_root + 1, right);return BTroot;}TreeNode* buildTree(const vector<int>& preorder, vector<int>& inorder) {//inorder填充hashfor (int i = 0; i < inorder.size(); i++){hash[inorder[i]] = i;}return dfs(preorder, 0, 0, inorder.size() - 1);}
};