【算法】递归+深搜：105.从前序与中序遍历序列构造二叉树

目录

1、题目链接

2、题目介绍

​​3、解法

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

函数体---解决子问题

4、代码

---

1、题目链接

105.从前序与中序遍历序列构造二叉树. - 力扣（LeetCode）

2、题目介绍

​
3、解法

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

因此，我们可以利用前序确定二叉树的根节点，中序遍历确定左、右子树的结点数。

1. 前序遍历的首元素 为 树的根节点 node 的值。
2. 在中序遍历中搜索根节点 node 的索引 ，可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ] 。
3. 根据中序遍历中的左（右）子树的节点数量，可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ] 。

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

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

参数： 根节点在前序遍历的索引 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);}
};