Tuesday, July 7, 2015

LeetCode OJ - Construct Binary Tree from Preorder and Inorder Traversal

Problem:

Please find the problem here.

Solution:

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.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

#include "LEET_CONSTRUCT_BINARY_TREE_FROM_PREORDER_AND_INORDER_TRAVERSAL.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

    class Solution
    {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
        {
            return buildTree(preorder, 0, preorder.size(), inorder, 0, inorder.size());
        }
    private:
        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])
                {
                    break;  
                }
            }
            // 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;
        }
    };
};

using namespace _LEET_CONSTRUCT_BINARY_TREE_FROM_PREORDER_AND_INORDER_TRAVERSAL;

int LEET_CONSTRUCT_BINARY_TREE_FROM_PREORDER_AND_INORDER_TRAVERSAL()
{
    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