<106> Construct Binary Tree from Inorder and Postorder Traversal

Posted on Edited on In Views:

Description

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

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

Leetcode link: 106. Construct Binary Tree from Inorder and Postorder Traversal

105. Construct Binary Tree from Inorder and Postorder Traversal (Related)

Idea

By observing in-order tree and post-order tree, we can see that their structures are like below:

1
2
3
4
5
6
7
8
9
// in-order
+------------+--------+-------------+
| left child | Parent | right child |
+------------+--------+-------------+  

// post-order
+------------+-------------+--------+
| left child | right child | Parent |
+------------+-------------+--------+

The parent node is always the last element in a post-order tree. We can find the parent node first, then split the in-order tree into two sub trees recursively according to the value of the parent node. The recursion stops when it reaches leaf nodes.

Solution

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
// Java, 4ms
/**
 * 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 {
    int[] inorderR;
    int[] postorderR;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.inorderR = inorder;
        this.postorderR = postorder;
        
        return buildTree(0, inorder.length-1, 0, postorder.length-1);
    }
    
    private TreeNode buildTree(int startIn, int endIn, int startPost, int endPost) {
        // find the parent node, then split the tree into
        // left sub tree and right sub tree recursively
        if (startIn > endIn || startPost > endPost)
            return null;
        
        int parentVal = this.postorderR[endPost];
        int parentIdx = 0;
        // bottleneck
        for (int i = 0; i <= endIn-startIn; i++) {
            if (this.inorderR[startIn+i] == parentVal) {
                parentIdx = i;
                break;
            }
        }
        
        TreeNode parentNode = new TreeNode(parentVal);
        parentNode.left  = buildTree(startIn, startIn+parentIdx-1, startPost, startPost+parentIdx-1);
        parentNode.right = buildTree(startIn+parentIdx+1, endIn, startPost+parentIdx, endPost-1);
        
        return parentNode;
    }
}

Improvement: with hashmap

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
// Java, 1ms
class Solution {
    int[] postorderR;
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorderR = postorder;
        this.map = new HashMap<Integer, Integer>();
        // store inorder indices into a hashmap
        for (int i = 0; i < inorder.length; i++)
            this.map.put(inorder[i], i);
        
        return buildTree(0, inorder.length-1, 0, postorder.length-1);
    }
    
    private TreeNode buildTree(int startIn, int endIn, int startPost, int endPost) {
        if (startIn > endIn || startPost > endPost)
            return null;
        
        int parentVal = postorderR[endPost];
        // use hashmap to get parent index faster
        int parentIdx = map.get(parentVal);
        
        TreeNode parentNode = new TreeNode(parentVal);
        parentNode.left  = buildTree(startIn, parentIdx-1, startPost, startPost+parentIdx-1-startIn);
        parentNode.right = buildTree(parentIdx+1, endIn, startPost+parentIdx-startIn, endPost-1);
        
        return parentNode;
    }
}