Construct Binary Tree from Preorder and Inorder Traversal

• If the preorder array is empty, return null.
• The first element of the preorder array, preorder[0], is the root of the tree. Create a TreeNode for this root.
• Find the index, mid, of the root's value in the inorder array. This is a linear scan.
• The elements to the left of mid in the inorder array form the left subtree. The elements to the right form the right subtree.
• The number of nodes in the left subtree is mid.
• Create new subarrays for the left and right subtrees:
  • left_inorder: inorder from index 0 to mid - 1.
  • right_inorder: inorder from index mid + 1 to the end.
  • left_preorder: preorder from index 1 to mid.
  • right_preorder: preorder from index mid + 1 to the end.
• Recursively call the function to build the left child: root.left = buildTree(left_preorder, left_inorder).
• Recursively call the function to build the right child: root.right = buildTree(right_preorder, right_inorder).
• Return the root node.

The core idea is to use recursion. The base case for the recursion is when the input arrays are empty, in which case we return null.

In each recursive step:

1. Pick the first element from the preorder array. This is the root of the current subtree.
2. Create a new TreeNode with this value.
3. Search for this root's value in the inorder array. Let's say its index is k.
4. All elements in the inorder array to the left of k (from index 0 to k-1) belong to the left subtree.
5. All elements in the inorder array to the right of k (from index k+1 to the end) belong to the right subtree.
6. The number of elements in the left subtree is k.
7. The next k elements in the preorder array (after the root) belong to the left subtree's preorder traversal. The rest belong to the right subtree's preorder traversal.
8. Create new subarrays for the left and right subtrees' traversals (left_inorder, right_inorder, left_preorder, right_preorder).
9. Recursively call the function to build the left and right children.

This process is simple to understand but inefficient due to the repeated creation of new arrays and linear scanning in each recursive call.

1import java.util.Arrays;2 3/**4 * Definition for a binary tree node.5 * public class TreeNode {6 *     int val;7 *     TreeNode left;8 *     TreeNode right;9 *     TreeNode() {}10 *     TreeNode(int val) { this.val = val; }11 *     TreeNode(int val, TreeNode left, TreeNode right) {12 *         this.val = val;13 *         this.left = left;14 *         this.right = right;15 *     }16 * }17 */18class Solution {19    public TreeNode buildTree(int[] preorder, int[] inorder) {20        if (preorder == null || preorder.length == 0) {21            return null;22        }23 24        // The first element of preorder is the root25        TreeNode root = new TreeNode(preorder[0]);26 27        // Find the root in the inorder array28        int mid = -1;29        for (int i = 0; i < inorder.length; i++) {30            if (inorder[i] == root.val) {31                mid = i;32                break;33            }34        }35 36        // Create subarrays for left and right subtrees37        int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid);38        int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, inorder.length);39        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, mid + 1);40        int[] rightPreorder = Arrays.copyOfRange(preorder, mid + 1, preorder.length);41 42        // Recursively build the left and right subtrees43        root.left = buildTree(leftPreorder, leftInorder);44        root.right = buildTree(rightPreorder, rightInorder);45 46        return root;47    }48}