leetcode 从前序与中序遍历序列构造二叉树 中等
以 前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6} 为例：
我们知道前序遍历是 先根后左再右，而中序遍历是 先左后根再右。所以我们很容易可以算出左子树和右子树的子树大小。
如例子：对于整个序列，我们知道 1 是根节点。
在中序遍历中，1 的下标是 3，所以 1 节点的左子树大小是 3，右子树的大小是 4
然后原中序序列就被分成了两部分：4 7 2，5 3 8 6 (分别表示左子树和右子树)
根据子树大小，前序序列也分成两部分：2 4 7, 3 5 6 8 (分别表示左子树和右子树)
很容易知道，1 的左儿子就是 2，右儿子是 3.
接着对上面两个序列做相同的操作，就可以重建出最开始的二叉树了。
需要提的一点：我们并不需要真正的分割两个序列，只需要分别引入两个下标即可。
题目中有说道，val 是不重复的。所以我们直接用 unordered_map 存储每个 val 在中序序列中的下标即可
其他的组合：如后序+中序，做法也是同理的。
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.size() == 0) return nullptr; for(int i = 0; i < inorder.size(); ++ i) map[inorder[i]] = i; return _buildTree(preorder, inorder, 0, preorder.size() - 1, 0, preorder.size() - 1); } TreeNode* _buildTree(vector<int> &preorder, vector<int> &inorder, int l, int r, int ll, int rr) { // [l, r] 前序的区间, [ll, rr] 中序的区间 if(l > r) return nullptr; TreeNode* root = new TreeNode(preorder[l], nullptr, nullptr); root -> left = _buildTree(preorder, inorder, l + 1, l + map[preorder[l]] - ll, ll, map[preorder[l]] - 1); root -> right = _buildTree(preorder, inorder, l + map[preorder[l]] - ll + 1, r, map[preorder[l]] + 1, rr); return root; } unordered_map<int, int> map; // 某个 val 在 inorder 中的下标 };
原文：https://www.cnblogs.com/rookie-acmer/p/15302855.html