Construct Binary Tree from Preorder and Postorder Traversal LeetCode solution in Java

1
class Solution {
2
  public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
3
    // O(n) time | O(h) space
4
    if (preorder == null || postorder == null || preorder.length == 0 || postorder.length == 0)
5
      return null;
6

7
    TreeNode root = new TreeNode(preorder[0]);
8
    int mid = 0;
9

10
    if (preorder.length == 1) return root;
11

12
    // update mid
13
    for (int i = 0; i < postorder.length; i++) {
14
      if (preorder[1] == postorder[i]) {
15
        mid = i;
16
        break;
17
      }
18
    }
19

20
    root.left =
21
        constructFromPrePost(
22
            Arrays.copyOfRange(preorder, 1, 1 + mid + 1),
23
            Arrays.copyOfRange(postorder, 0, mid + 1));
24

25
    root.right =
26
        constructFromPrePost(
27
            Arrays.copyOfRange(preorder, 1 + mid + 1, preorder.length),
28
            Arrays.copyOfRange(postorder, mid + 1, postorder.length - 1));
29
    return root;
30
  }
31
}