LeetCode Construct Binary Tree from Inorder and Postorder/Preorder Traversal: DFS

Overview

LeetCode Construct Binary Tree from Inorder and Postorder/Preorder Traversal: DFS, inorder determine the left/right subtree while pre/postorder determine the root.

LeetCode Construct Binary Tree from Inorder and Postorder/Preorder Traversal

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

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

Solution: DFS

We can always construct the binary tree from inorder and postorder (or preorder) travsersal, but we cannot construct the tree from postorder and preorder. This is because either postorder or preorder traversal only gives the information about where the root is, only inorder traversal provides the information about where the left subtree and the right subtree is, so for all these kinds of problems, the inorder traversal is needed.

The solution itself is not difficult to verify, it is just like: in the postorder traversal, the last element is the root (for preorder, then the first element is the root), and we then find this element is the inorder traversal, the left part to this element is the inorder traveral is the left subtree, and the right side is the right subtree. We then apply recursive call on the corresponding left and right subtree. To quickly determine where the element is in the inorder traversal, one could first build a hash table to store the index. The following code implements this idea and could be accepted by the LeetCode OJ to pass both  Construct Binary Tree from Inorder and Postorder/Preorder Traversal problems:

class Solution {
    public:
        unordered_map<int, int> inorderPositions;

        TreeNode *buildInner(const vector<int> &preorder, int l1,
                             const vector<int> &inorder,  int l2, int n) {
            if (n <= 0)
                return NULL;
            int rootValue = preorder[l1];

            TreeNode *root = new TreeNode(rootValue);
            int inorderPos = inorderPositions[rootValue];

            int lLength = inorderPos - l2;
            int rLength = n - lLength - 1;

            root->left  = buildInner(preorder, l1 + 1, inorder, l2, lLength);
            root->right = buildInner(preorder, l1 + lLength + 1, inorder, inorderPos + 1, rLength);
            return root;
        }

        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

            if (preorder.size() != inorder.size()) return NULL;

            int n = preorder.size();

            inorderPositions.clear();
            for (int i = 0; i < n; ++i)
                inorderPositions[inorder[i]] = i;

            return buildInner(preorder, 0, inorder, 0, n);
        }
};

And the following is for postorder which is quite similar:

class Solution {
    public:

        unordered_map<int, int> inorderPositions;
        TreeNode *buildInner(const vector<int> &inorder, int s1,
                             const vector<int> &postorder, int s2, int len) {
            if (len <= 0)
                return NULL;

            int rootValue = postorder[s2+len-1];
            int inorderPos = inorderPositions[rootValue];

            TreeNode *root = new TreeNode(rootValue);
            int lLength = inorderPos - s1;

            root->left  = buildInner(inorder, s1, postorder, s2, lLength);
            root->right = buildInner(inorder, inorderPos + 1, postorder, s2 + lLength, len - lLength - 1);
        }

        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            if (inorder.size() != postorder.size())
                return NULL;

            int n = inorder.size();
            inorderPositions.clear();
            for (int i = 0; i < n; ++i)
                inorderPositions[inorder[i]] = i;

            return buildInner(inorder, 0, postorder, 0, n);
        }
};

Remarks: 

  1. If there are duplicates in the input, then the bianry tree would not be unique
  2. The iterative approach exists for these two problems, but is non-trivial to come up with, any good explanation and easy to understand implementation references !?

Reference: Construct Binary Tree From Inorder and Preorder/Postorder Traversal

Summary

LeetCode Construct Binary Tree from Inorder and Postorder/Preorder Traversal: DFS, inorder determine the left/right subtree while pre/postorder determine the root.

Written on April 17, 2013