Create an unique binary tree from given inorder and postorder traversal (code in JAVA)
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int data) {
this.data = data;
left = right = null;
}
}
public class h {
public static TreeNode newNode(int data) {
return new TreeNode(data);
}
public static TreeNode constructTree(int[] postorder, int postStart, int postEnd,
int[] inorder, int inStart, int inEnd, Map<Integer, Integer> mp) {
if (postStart > postEnd || inStart > inEnd) return null;
TreeNode root = newNode(postorder[postEnd]);
int elem = mp.get(root.data);
int nElem = elem - inStart;
root.left = constructTree(postorder, postStart, postStart + nElem - 1,
inorder, inStart, elem - 1, mp);
root.right = constructTree(postorder, postStart + nElem, postEnd - 1, inorder,
elem + 1, inEnd, mp);
return root;
}
public static TreeNode buildTree(int[] postorder, int[] inorder) {
int postStart = 0, postEnd = postorder.length - 1;
int inStart = 0, inEnd = inorder.length - 1;
Map<Integer, Integer> mp = new HashMap<>();
for (int i = inStart; i <= inEnd; i++) {
mp.put(inorder[i], i);
}
return constructTree(postorder, postStart, postEnd, inorder, inStart, inEnd, mp);
}
//levelorder traversal
public static void levelorder(TreeNode root)
{
if(root==null) return;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
q.add(null);
while(!q.isEmpty())
{
TreeNode currnode = q.remove();
if(currnode==null) //NULL DENOTES NEW LINE
{
System.out.println();
if(q.isEmpty())
{
break;
}
else
{
q.add(null);
}
}
else
{
System.out.print(currnode.data+" ");
if(currnode.left!=null)
{
q.add(currnode.left);
}
if(currnode.right!=null)
{
q.add(currnode.right);
}
}
}
}
public static void main(String[] args) {
int[] postorder = {11,8,1,3,4,2,5};
int[] inorder = {11,1,8,5,3,2,4};
TreeNode root = buildTree(postorder, inorder);
levelorder(root);
}
}
No comments:
Post a Comment