105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
根据树的先序遍历和中序遍历结果，重构这棵树。 其实大学的时候就有这样的作业，如果在纸上做，还是很简单的，但要实现成代码，稍微有点难理清这里的关系。 我们先来看一个纸上的解题过程，假设有下面这样一棵树：
3
/ \
9 20
/ \ / \
1 2 15 17
- 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
- 中序遍历结果为：1, 9, 2, 3, 15, 20, 17
首先我们可以根据先序遍历结果找到根节点3，然后在中序遍历中看看3所处的位置，那么3左边的就是左孩子节点，右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点，说明3的左子树共有3个节点，同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树，再后面3个节点是右子树，这样就把两个遍历结果分成了两部分：
- 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
- 中序遍历结果为：1, 9, 2, 3, 15, 20, 17
在红色部分递归就是3的左子树，在蓝色部分递归就是3的右子树。 纸上解题好说，但是代码实现，我开始还把自己搞糊涂了，代码很复杂，后来参考了这位大神的博客，代码好简洁易懂，赞一个：
class Solution {
private:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash)
{
if (preL > preR || inL > inR)
return NULL;
TreeNode* root = new TreeNode(preorder[preL]);
size_t idx = hash[root->val];
root->left = dfs(preorder, inorder, preL + 1, idx – inL + preL, inL, idx – 1, hash);
root->right = dfs(preorder, inorder, idx – inL + preL + 1, preR, idx + 1, inR, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
if (preorder.size() == 0)
return NULL;
unordered_map<int, size_t> hash;
for (size_t i = 0; i < inorder.size(); ++i) {
hash[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, preorder.size() – 1, 0, inorder.size() – 1, hash);
}
};
本代码提交AC，用时16MS。
代码中有两点需要注意的，一是为了在中序遍历中快速找到根节点，提前对中序遍历结果hash了，因为题目中说了不会有重复元素；二是在dfs递归的时候，要算好下标的起止位置，一定不要弄错了，特别是preorder在左右子树中的起止位置。
完整代码如下：
[cpp]
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)return "";
string ans = to_string(root->val);
if (root->left) ans += ","+serialize(root->left);
if (root->right) ans += ","+serialize(root->right);
return ans;
}
void insert(TreeNode* root, TreeNode* node) {
if (node->val < root->val) {
if (root->left == NULL)root->left = node;
else insert(root->left, node);
}
else {
if (root->right == NULL)root->right = node;
else insert(root->right, node);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "")return NULL;
TreeNode* root = NULL;
for (int start = 0, end = 0; end <= data.size(); ++end) {
if (data[end] == ‘,’ || end == data.size()) {
TreeNode* node = new TreeNode(atoi(data.substr(start, end – start).c_str()));
if (root == NULL)root = node;
else insert(root, node);
start = end + 1;
}
}
return root;
}
};
[/cpp]
本代码提交AC，用时26MS。]]>