Construct Binary Treefrom Preorderand Inorder Traversal Algorithm
The Construct Binary Tree from Preorder and Inorder Traversal Algorithm is an efficient method to construct a binary tree from given preorder and inorder traversal sequences. Preorder traversal is the process of visiting the root node first, and then its left subtree, followed by the right subtree. Inorder traversal, on the other hand, visits the left subtree first, followed by the root node, and then the right subtree. By using these two traversal sequences, the algorithm uniquely constructs the binary tree that generated those sequences.
The algorithm starts by finding the root node of the tree, which is the first element in the preorder sequence. Then, it identifies the position of the root node in the inorder sequence, which divides the sequence into left and right subtrees. The left subtree will have elements before the root node in the inorder sequence and the right subtree will have elements after the root node. Recursively, the algorithm constructs the left subtree by using the corresponding elements from the preorder and inorder sequences and then constructs the right subtree similarly. This process is repeated until the entire tree is constructed. The algorithm has a time complexity of O(n), where n is the number of nodes in the tree, making it an efficient and effective method for reconstructing a binary tree from its 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> &preorder, vector<int> &inorder) {
if (preorder.size() == 0) {
return NULL;
}
return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* dfs(vector<int>& preorder, int l1, int r1, vector<int>& inorder, int l2, int r2) {
if (l1 > r1) {
return NULL;
}
if (l1 == r1) {
return new TreeNode(preorder[l1]);
}
TreeNode* root = new TreeNode(preorder[l1]);
for (int i = l2; i <= r2; i++) {
if (inorder[i] == preorder[l1]) {
root->left = dfs(preorder, l1 + 1, l1 + i - l2, inorder, l2, i - 1);
root->right = dfs(preorder, l1 + i - l2 + 1, r1, inorder, i + 1, r2);
return root;
}
}
return NULL;
}
};
