Problem: 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.

 

 

 

    3

    / \

   9   20

       /   \

     15   7

 

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

 

Example 2:

Input: preorder = [-1], inorder = [-1]

Output: [-1]

 

Solution:

Node BuildTree(char[] Preorder, char[] InOrder, int index = 0)
{
 Node root = new Node();
 root.data = PreOrder[index];
 root.left = null;
 root.right = null;

 int inIndex = Arrays,asList(InOrder).indexOf(Preorder[index]);

 if ( index+1 < Preorder.Length &&
       IsLeftSubtree(Preorder[index+1], inOrder, inIndex) == true)
       root.left = BuildTree(Preorder, InOrder, index + 1);

 if ( inIndex+1 < InOrder.Length &&
       isPredecessor(InOrder[inIndex+1], Preorder, index) == false)
       root.right = BuildTree(Preorder, InOrder, Arrays.asList(PreOrder).indexOf(InOrder[inIndex + 1]));

 return root;

}

boolean is Predecessor(char c, char[] Preorder, int index)
{
return Arrays.asList(Preorder).indexOf(c) < index;
}

boolean isLeftSubtree(char c, char[] inOrder, int index)
{
Arrays.asList(Inorder).indexOf(c) < index;
}