online advertising

Tuesday, July 7, 2015

LeetCode OJ - Construct Binary Tree from Preorder and Inorder Traversal


Please find the problem here.


The root is really easy to find. It is simply the 1st element in the preorder traversal.

Given the root, it is easy to split the in-order list into two halves, left hand side of the root is the left sub-tree, right hand side of the root is the right sub-tree.

Now here is the key observation. It is easy to split the pre-order list into the left sub-tree and right sub-tree too, how? We know the size of the left sub-tree!

The rest is just recursion, which is trivial.


#include "stdafx.h"


#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

    struct TreeNode 
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}

    class Solution
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
            return buildTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());
        TreeNode* buildTree(vector<int>& preorder, unsigned int preorderStart, unsigned int preorderEnds, vector<int>& inorder, unsigned int inorderStart, unsigned int inorderEnds)
            if (preorderStart >= preorderEnds)
                return NULL;
            unsigned int inorderIndex = inorderStart;             
            for (;inorderIndex < inorderEnds; inorderIndex++)
                if (inorder[inorderIndex] == preorder[preorderStart])
            // inOrder [inorderStart, inorderIndex) is the left subtree.
            // inOrder [inorderIndex + 1, inorderEnds) is the right subtree.
            int leftSubTreeSize = inorderIndex - inorderStart;
            unsigned int preorderIndex = preorderStart + 1 + leftSubTreeSize;

            TreeNode* result = new TreeNode(preorder[preorderStart]);
            result->left = buildTree(preorder, preorderStart + 1, preorderIndex, inorder, inorderStart, inorderIndex);
            result->right = buildTree(preorder, preorderIndex, preorderEnds, inorder, inorderIndex + 1, inorderEnds);
            return result;


    Solution solution;
    int preorderArray[2] = { 1, 2 };
    int inorderArray[2] = { 2, 1 };
    vector<int> preorder(preorderArray, preorderArray + 2);
    vector<int> inorder(inorderArray, inorderArray + 2);
    TreeNode* result = solution.buildTree(preorder, inorder);
    return 0;

No comments :

Post a Comment