https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
这道题已知中序遍历和前序遍历的结果求二叉树。我们发现中序遍历结果和前序遍历结果的结构如下。 中序遍历结果的结构：[左子树中序遍历结果] + 根节点 + [右子树中序遍历结果] 前序遍历结果的结构：根节点 + [左子树前序遍历结果] + [右子树前序遍历结果] 也就是说前序遍历结果的第一个元素就是根节点，根据这个根节点在中序遍历结果里面找到对应的节点就可以把中序遍历结果分成左右两棵子树；再根据这两棵子树的长度就可以把前序遍历结果的左右子树序列分开。再用该方法依次迭代各个子树，就可以建立完整的二叉树。
以下代码为了加速查询建立了一张map缓存中序遍历和位置的对应关系，代码的时间复杂度是O(n)，空间复杂度是O(n)。
class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if (preorder.empty() || inorder.empty()) return NULL; map<int, int> inorderMap; for (int i=0; i<inorder.size(); ++i) inorderMap[inorder[i]] = i; return helper( preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, inorderMap ); } TreeNode* helper(vector<int>& preorder, int preL, int preR, vector<int>& inorder, int inL, int inR, map<int, int>& inorderMap) { if (preL > preR || inL > inR) return NULL; TreeNode* root = new TreeNode( preorder[preL] ); int index = inorderMap[preorder[preL]]; root->left = helper( preorder, preL+1, preL+index-inL, inorder, inL, index-1, inorderMap); root->right = helper( preorder, preL+index-inL+1, preR, inorder, index+1, inR, inorderMap); return root; } }; class Solution: def __init__(self): self.inorderMap = {} def buildTree(self, preorder, inorder): if preorder is None or len(preorder) == 0 or inorder is None or len(inorder) == 0: return None for i in range(len(inorder)): self.inorderMap[inorder[i]] = i return self.helper(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1) def helper(self, preorder, pL, pR, inorder, iL, iR): if pL > pR or iL > iR: return None root = TreeNode(preorder[pL]) root.left = self.helper(preorder, pL+1,pL+self.inorderMap[root.val]-iL, inorder, iL, self.inorderMap[root.val]-1) root.right = self.helper(preorder, pL+self.inorderMap[root.val]-iL+1, pR, inorder, self.inorderMap[root.val]+1, iR) return root
