[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal

Posted on | In

Problem

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

Note:

You may assume that duplicates do not exist in the tree.

For example, given

1
2
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

Explanation 1

  1. Similar to 105. Construct Binary Tree from Preorder and Inorder Traversal, this time, we know the root node is the end element of postorder array, and we can find the root element in the inorder array, then we can know the range of leftsubtree and rightsubtree. One example is below:
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
Inorder:　　 　11　　4　　5　　13　　8　　9

Postorder:　　11　　4　　13　　9　　8　　5　　



11　　4　　5　　13　　8　　9　　　　　　=>　　　　　　　　　 5

11　　4　　13　　9　　8　　5　　　　　　　　　　　　　　　　/　　\



11　　4　　 　　13　　 8　　9　　　　　　=>　　　　　　　　　5

11　　4　　　　 13　　 9　　8　　　　　　　　　　　　　　　/　　\

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  4　　　8



11　　　　 　　13　　　　9　　　　　　　　=>　　　　　　　　　5

11　　　　　　 13　　　　9　　　　 　　　　　　　　　　　　 /　　\

　　　　　　　　　　　　　　　　　 　　　　　　　　　　　   4　　　8

　　　　　　　　　　　　　　　　　　　　　　　　　　　　 /　　　 /     \

　　　　　　　　　　　　　　　　　　　　　　　　　　　  11　　  13　　  9

Solution 1

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode helper(int[] inorder, int[] postorder, int postStart, int postEnd, int inStart, int inEnd) {
        if (postEnd < 0 || inStart > inEnd) return null;
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        int i = inStart;
        while (i <= inEnd) {
            if (inorder[i] == rootVal) break;
            i++;
        }
        root.left = helper(inorder, postorder, postStart, postStart+(i-inStart)-1, inStart, i-1);
        root.right = helper(inorder, postorder, postStart+(i-inStart), postEnd-1, i+1, inEnd);
        return root;
    }

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

Explanation 2

  1. Using the while loop to find the root value’s index in inorder[] in each recursion call make the time complexity be $O(n^2)$. We can reduce the time complexity to $O(n)$ by using a HashMap to record the key is the element, value is the element’s index.

  2. We can also remove the postStart since we only need to find the root from postorder[] by using postEnd.

Solution 2

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode helper(int[] inorder, int[] postorder, int left, int right, int rootIdx, Map<Integer, Integer> hm) {
        if (left > right) return null;
        if (left == right) return new TreeNode(postorder[rootIdx]);

        TreeNode root = new TreeNode(postorder[rootIdx]);

        int inorderRootIdx = hm.get(postorder[rootIdx]);

        root.right = helper(inorder, postorder, inorderRootIdx+1, right, rootIdx-1, hm);
        root.left = helper(inorder, postorder, left, inorderRootIdx-1, rootIdx - (right - inorderRootIdx + 1), hm);

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