105. Construct Binary Tree from Preorder and Inorder Traversal(构建二叉树) [LeetCode]
105. Construct Binary Tree from Preorder and Inorder Traversal
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
画了一个复杂点的二叉树来剖析本题的递归，注意尾递归不在搜索范围内，只是用来确定边界，边界一定要考虑清除！
class Solution {
public:
TreeNode * buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(begin(preorder), end(preorder),begin(inorder), end(inorder));
}
template<typename T>
TreeNode* buildTree(T pre_first, T pre_last,T in_first, T in_last) {
if (pre_first == pre_last|| in_first == in_last) return nullptr;
auto root = new TreeNode(*pre_first);
auto RootPos = find(in_first, in_last, root->val);
auto leftSize = distance(in_first, RootPos);
auto boundary = next(pre_first, leftSize+1);
root->left = buildTree(next(pre_first), boundary, in_first, RootPos);
root->right = buildTree(boundary, pre_last, next(RootPos), in_last);
return root;
}
};
106. Construct Binary Tree from Inorder and Postorder Traversal
given
inorder = [9,3,15,20,7] postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
同样以上面的图为例来说明：
class Solution {
public:
TreeNode * buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(begin(inorder), end(inorder), begin(postorder), end(postorder));
}
template<typename T>
TreeNode* buildTree(T in_first, T in_last, T post_first, T post_last) {
if (in_first == in_last || post_first == post_last)return nullptr;
const int val = *prev(post_last);
TreeNode *root = new TreeNode(val);
auto rootPos = find(in_first, in_last, val);
auto leftsize = distance(in_first, rootPos);
auto boundary = next(post_first, leftsize);
root->left = buildTree(in_first, rootPos, post_first, boundary);
root->right = buildTree(next(rootPos), in_last, boundary, prev(post_last));
return root;
}
};