105. 从前序与中序遍历序列构造二叉树
描述
- 根据一棵树的前序遍历与中序遍历构造二叉树。
- 注意：你可以假设树中没有重复的元素。
示例
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
思路
- 前序遍历中的第一个元素为根节点，中序遍历中根节点左边的元素为左子树，右边的元素为右子树。先序遍历中前leftLen个元素为左子树，后面的元素为右子树，而构建子树的过程又是递归的。
1)找到根节点在中序遍历中的位置iRoot
2)计算leftLen = iRoot - iStart
3)左子树为preOrder[pStart + 1, pStart + leftLen], inOrder[iStart, iRoot - 1]
4)右子树为preOrder[pStart + leftLen + 1, pEnd], inOrder[iRoot + 1, iEnd]
5)当iStart > iEnd 时退出递归，返回NULL
- 小技巧，空间换时间。利用一个map保存中序遍历中每个元素的小标，这要在找根节点在中序遍历中的Index时就不用每次都遍历了。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int size = preorder.size();
for (int i = 0; i < size; ++i) {
dict[inorder[i]] = i;
}
return _buildTree(preorder, 0, size - 1, inorder, 0, size - 1);
}
TreeNode* _buildTree(vector<int>& preorder, int pStart, int pEnd,
vector<int>& inorder, int iStart, int iEnd) {
if (iStart > iEnd) return NULL;
int rootVal = preorder[pStart];
int iRoot = dict[rootVal];
int leftLen = iRoot - iStart;
TreeNode* pNode = new TreeNode(rootVal);
pNode->left = _buildTree(preorder, pStart + 1, pStart + leftLen, inorder,
iStart, iRoot - 1);
pNode->right = _buildTree(preorder, pStart + leftLen + 1, pEnd, inorder,
iRoot + 1, iEnd);
return pNode;
}
private:
unordered_map<int, int> dict;
};
