106. Construct Binary Tree from Inorder and Postorder Traversal
1. Description
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
2. Example
Example 1
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2
Input: inorder = [-1], postorder = [-1]
Output: [-1]
3. Constraints
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder and postorder consist of unique values.
- Each value of postorder also appears in inorder.
- inorder is guaranteed to be the inorder traversal of the tree.
- postorder is guaranteed to be the postorder traversal of the tree.
4. Solutions
Recursion
n = postorder.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
TreeNode *buildTree(const vector<int> &inorder, const vector<int> &postorder) {
const int n = inorder.size();
unordered_map<int, int> in_node_index;
in_node_index.reserve(n);
for (int i = 0; i < n; ++i) {
in_node_index.emplace(inorder[i], i);
}
return build_tree(0, n - 1, in_node_index, postorder, 0, n - 1);
}
private:
TreeNode *build_tree(
int in_left,
int in_right, // include
const unordered_map<int, int> &in_node_index,
const vector<int> &postorder,
int post_left,
int post_right) {
if (post_left <= post_right) {
TreeNode *root = new TreeNode(postorder[post_right]);
int index = in_node_index.at(postorder[post_right]);
root->left = build_tree(
in_left,
index - 1,
in_node_index,
postorder,
post_left,
post_left + index - in_left - 1);
root->right = build_tree(
index + 1,
in_right,
in_node_index,
postorder,
post_left + index - in_left,
post_right - 1);
return root;
} else {
return nullptr;
}
}
};