Construct Binary Tree from Inorder and Postorder/Preorder Traversal
From INORDER and POSTORDER
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.
Algorithm:
In Postorder, the rightmost element is the root. Search this root in inorder array .Let that index be i ,then left side of i is left subtree and right side of i is right subtree. We use postorder array to create nodes but to construct tree we use inorder array.
Code:
class Solution {
int index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index= postorder.length-1;
return build(postorder,inorder,0,postorder.length-1);
}
public TreeNode build(int[] post, int[] in, int start, int end){
if(start>end){
return null;
}
TreeNode node = new TreeNode(post[index]);
index--;
int inIndex=search(in,start,end,node.val);
node.right=build(post,in,inIndex+1,end);
node.left=build(post,in,start,inIndex-1);
return node;
}
public int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
return i;
}
}
From INORDER and PREORDER
Given two integer arrays preorder
and inorder
where preorder
is the preorder traversal of a binary tree and inorder
is the inorder traversal of the same tree, construct and return the binary tree.
Code:
class Solution {
int index=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder,inorder,0,preorder.length-1);
}
public TreeNode build(int[] pre, int[] in, int start, int end){
if(start>end){
return null;
}
TreeNode node = new TreeNode(pre[index]);
index++;
if(start==end){
return node;
}
int inIndex=search(in,start,end,node.val);
node.left=build(pre,in,start,inIndex-1);
node.right=build(pre,in,inIndex+1,end);
return node;
}
public int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i;
}
return i;
}
}