889. Construct Binary Tree from Preorder and Postorder Traversal
1. Description
Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
2. Example
Example 1:
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Example 2:
Input: preorder = [1], postorder = [1]
Output: [1]
3. Constraints
- 1 <= preorder.length <= 30
- 1 <= preorder[i] <= preorder.length
- All the values of preorder are unique.
- postorder.length == preorder.length
- 1 <= postorder[i] <= postorder.length
- All the values of postorder are unique.
- It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
4. Solutions
Brute Force
n = preorder.size()
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution {
public:
TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
return construct_(preorder, 0, preorder.size() - 1, postorder, 0, postorder.size() - 1);
}
private:
TreeNode *construct_(
const vector<int> &preorder,
int pre_left,
int pre_right,
const vector<int> &postorder,
int post_left,
int post_right) {
if (pre_left <= pre_right) {
int root_value = preorder[pre_left]; // postorder[post_right]
auto root = new TreeNode(root_value);
if (pre_left < pre_right) {
int left_child_value = preorder[pre_left + 1];
int left_child_index = post_left;
while (left_child_index <= post_right &&
postorder[left_child_index] != left_child_value) {
++left_child_index;
}
root->left = construct_(
preorder,
pre_left + 1,
pre_left + 1 + (left_child_index - post_left),
postorder,
post_left,
left_child_index);
root->right = construct_(
preorder,
pre_left + 1 + (left_child_index - post_left) + 1,
pre_right,
postorder,
left_child_index + 1,
post_right - 1);
}
return root;
} else {
return nullptr;
}
}
};