Construct Binary Treefrom Inorderand Postorder Traversal Algorithm
The Construct Binary Tree from Inorder and Postorder Traversal Algorithm is a technique used to build a binary tree from its given inorder and postorder traversal sequences. Inorder traversal is a method of visiting the nodes of a binary tree in a specific order: left subtree, root, and then right subtree. Postorder traversal, on the other hand, visits the nodes in the order of left subtree, right subtree, and then root. The algorithm uses the unique properties of these traversal methods to efficiently reconstruct the original binary tree.
The algorithm begins by identifying the root node, which can be easily found as the last element in the postorder sequence. Then, the position of the root node in the inorder sequence is determined, effectively dividing the inorder sequence into two parts, i.e., the left subtree and the right subtree. This process is recursively applied to the left and right subtrees, using the updated inorder and postorder sequences, until the entire tree is reconstructed. The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree, making it an efficient method to reconstruct a binary tree from its inorder and postorder traversal sequences.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if (inorder.empty()) {
return NULL;
}
return dfs(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* dfs(vector<int>& inorder, int l1, int r1, vector<int>& postorder, int l2, int r2) {
if (l1 > r1) {
return NULL;
}
if (l1 == r1) {
return new TreeNode(inorder[l1]);
}
TreeNode* root = new TreeNode(postorder[r2]);
for (int i = l1; i <= r1; i++) {
if (inorder[i] == postorder[r2]) {
root->left = dfs(inorder, l1, i - 1, postorder, l2, l2 + i - l1 - 1);
root->right = dfs(inorder, i + 1, r1, postorder, l2 + i - l1, r2 - 1);
return root;
}
}
return NULL;
}
};
