Algorithm Problem 008: Construct Binary Tree from Preorder and Postorder Traversal (Solution 2)

Posted on In

Introduction

Readers may first want to read the previous article on this problem to understand the problem statement, the reasoning, and the solution.

Although I look down on a lot of my past code, the solution I wrote two years ago for this problem (Solution 1) seems to be the first one that genuinely made me "unbengable" (speechless). Today, when I came across this problem again, I only remembered that I had solved it before and even written a blog post about it, but I had completely forgotten the specific approach, so I had to start from scratch. In hindsight, that turned out to be a lucky thing.

The idea behind this problem is simple: given a postorder sequence $s_1, s_2, \cdots, s_a, \cdots, s_b, \cdots, s_n$, if $s_a$ appears before $s_b$, then $s_b$ can never be a child of $s_a$. The tricky part is how to translate that into code. In fact, the deeper question is: since the code for "Preorder and Inorder" and "Postorder and Inorder" is highly similar, why must the code for this problem ("Preorder and Postorder") be fundamentally so different?

This blog post presents Solution 2, which makes the code for all three binary-tree construction problems highly consistent, differing only in local details, and significantly improves readability.

Preorder and Postorder

The code for Solution 2 is as follows:

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
/**
 * 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:
    unordered_map<int, int> mp;
    int preIndex;
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        preIndex = 0;
        mp.clear();
        int n = postorder.size();
        for (int i = 0; i < n; ++i) {
            mp[postorder[i]] = i;
        }
        return dfs(preorder, postorder, -1);
    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& postorder, int parentIndex) {
        if (preIndex == preorder.size()) {
            return nullptr;
        }
        int curIndex = mp[preorder[preIndex]];
        // If the condition from the reasoning above is not satisfied, do not create
        // this subtree and backtrack to the parent's call frame.
        if (parentIndex >= 0) {
            if (curIndex > parentIndex) {
                return nullptr;
            }
        }
        TreeNode* ans = new TreeNode(preorder[preIndex++]);
        ans->left = dfs(preorder, postorder, curIndex);
        ans->right = dfs(preorder, postorder, curIndex);

        return ans;
    }
};

Looking at only this problem, the reader might not immediately understand why the code above is better. So I will show the code for "Preorder and Inorder" and "Postorder and Inorder" in the following sections, and then it will become clear.

Preorder and Inorder

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
class Solution {
public:
    int preIndex;
    unordered_map<int, int> inMap;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preIndex = 0;
        inMap.clear();
        int n = inorder.size();
        for (int i = 0; i < n; ++i) {
            inMap[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int val = preorder[preIndex++];
        TreeNode* ans = new TreeNode(val);
        int index = inMap[val];
        ans->left = dfs(preorder, inorder, left, index - 1);
        ans->right = dfs(preorder, inorder, index + 1, right);
        return ans;
    }
};

Postorder and Inorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int postIndex;
    unordered_map<int, int> mp;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        postIndex = n - 1;
        mp.clear();
        for (int i = 0; i < n; ++i) {
            mp[inorder[i]] = i;
        }
        return dfs(inorder, postorder, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        TreeNode* ans = new TreeNode(postorder[postIndex--]);
        int index = mp[ans->val];
        ans->right = dfs(inorder, postorder, index + 1, right);
        ans->left = dfs(inorder, postorder, left, index - 1);
        return ans;
    }
};

Postscript

I have seen the solutions of several well-known bloggers for "Preorder and Inorder" and "Postorder and Inorder", and they were all more complex than my code. Now I have unified "Preorder and Postorder" into this template as well, which I am very pleased with.