Algorithm Problem 006: Construct Binary Tree from Preorder and Postorder Traversal

Posted on In Word count in article: 705 Reading time ≈ 3 mins.

Problem

Problem Source：889. Construct Binary Tree from Preorder and Postorder Traversal(Daily Challenge)

Problem Description：

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

img

1
2
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

1
2
Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • All the values of preorder are unique.
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • All the values of postorder are unique.
  • It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Approach

Firstly, it is important to note that the binary tree constructed from preorder and postorder traversals is not unique, and therefore, there is no deterministic rule. In contrast, ‘inorder and preorder’ as well as ‘inorder and postorder’ correspond uniquely to a binary tree. These rules are clear, making coding straightforward. Hence, we need to define our own rules.

Recall that when constructing a binary tree from ‘inorder and preorder’, we sequentially traverse the preorder list. For each value, we create a corresponding node and then determine its subtree based on the inorder traversal. This can be understood as creating the preorder and verifying with the inorder.

Similarly, in this problem, we also ‘sequentially traverse the preorder list, creating a corresponding node’ but determine the position of the node (instead of its subtree) based on the postorder traversal. This is creating the preorder and verifying with the postorder.

In preorder, the sequence is “root - left - right”, and for each node in preorder, we can try placing it as the left child. In postorder, the sequence is “left - right - root”. If a node A in postorder is after node B, then A cannot be in the left subtree of B.

For example, consider node 5 in Example 1. While sequentially traversing the preorder list, we can try placing 5 as the left child of 4. However, in the postorder list, since 5 comes after 4, this attempt is not allowed. 5 can only be in the right subtree of one of the ancestors of 4, in this case, the right child of 2.

Therefore, we need to keep track of the path from the root to the last traversed node and store them in a stack.

  • As long as the current node and the top node of the stack do not satisfy the postorder constraint mentioned above, we pop the stack until it is satisfied. At this point, the current node becomes the right child of the top node.
  • If the constraint is already satisfied, the current node directly becomes the left child of the top node.

Code

The above approach is a rough description, and we should pay attention to details.

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n = preorder.size();
        // Only operate on the vector's tail, equivalent to a stack
        vector<TreeNode*> ve;
        unordered_map<int, int> mp;
        // Just like 'inorder and preorder', store <element, index> in the hash table for validation
        for (int i = 0; i < n; ++i) {
            mp[postorder[i]] = i;
        }
        for (int v: preorder) {
            TreeNode* cur = new TreeNode(v);
            // Only the first element (root) will trigger this condition
            if (ve.empty()) {
                ve.push_back(cur);
                continue;
            }
            bool popped = false;
            while((!ve.empty()) && (mp[v] > mp[ve.back()->val])) {
                ve.pop_back();
                popped = true;
            }
            if (!popped) {
                ve.back()->left = cur;
            } else {
                ve.back()->right = cur;
            }
            // Store the current node for the validation of the next node
            ve.push_back(cur);
        }
        // The first node is always the root node and will never be popped
        return ve.front();
    }
};

Time Complexity: $O(n)$

  • Sequentially traverse preorder and postorder.
  • Each node enters and exits ve only once.

Space Complexity: $O(n)$

  • mp stores the values and their indices of all $n$ nodes.
  • In the worst case, all nodes are in ve.