2.14 Construct Binary Tree from Preorder and Inorder Traversal

Description

Given preorder and inorder traversal of a tree, construct the binary tree.

Method

for preorder the fist elements of a entry is a root, and then we can use val to split inorder into two components, leftside is the left subtree ,rightside is the right subtree

Time and Space Complexity

o(n + n ^2)

Code

public class Solution {

public TreeNode buildTree(int[] preorder, int[] inorder) {
       if (preorder == null || inorder == null){
           return null;
       }
       if (inorder.length != preorder.length){
           return null;
       }
       return helper(preorder, 0, inorder, 0, inorder.length - 1);

}

public TreeNode helper(int[] preorder, int index, int[] inorder, int s, int e){
       if (s > e){
           return null;
       }
       int val = preorder[index];
       TreeNode root = new TreeNode(val);
       int mid = s;
       for (; mid <= e; mid++){
           if (inorder[mid] == val){
               break;
           }
       }

       root.left = helper(preorder, index + 1, inorder, s, mid - 1);
       root.right = helper(preorder, index + (mid - s) + 1, inorder, mid + 1, e);
       return root;
}

}