leetcode/java/0106-construct-binary-tree-from-inorder-and-postorder-traversal.java at main · neetcode-gh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> inMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        return helper(
            inorder,
            0,
            inorder.length - 1,
            postorder,
            0,
            postorder.length - 1,
            inMap
        );
    }

    public TreeNode helper(
        int[] inorder,
        int iStart,
        int iEnd,
        int[] postorder,
        int pStart,
        int pEnd,
        HashMap<Integer, Integer> inMap
    ) {
        if (pStart > pEnd || iStart > iEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[pEnd]);
        int index = inMap.get(postorder[pEnd]);
        int numsLeft = index - iStart;
        root.left =
            helper(
                inorder,
                iStart,
                index - 1,
                postorder,
                pStart,
                pStart + numsLeft - 1,
                inMap
            );
        root.right =
            helper(
                inorder,
                index + 1,
                iEnd,
                postorder,
                pStart + numsLeft,
                pEnd - 1,
                inMap
            );
        return root;
    }
}