LeetCode(105) Construct Binary Tree from Preorder and Inorder Traversal

제목

Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.

분석

두 갈래 나무의 앞 순서와 중간 순서를 정해서 이 두 갈래 나무를 구하세요.
우리는 수동으로 이런 문제를 많이 만들어서 그 규칙을 익혔다~
첫 번째 요소가 트리인 루트 노드를 앞뒤로 훑어보고 중간 순서에서 이 값을 찾습니다. 요소의 왼쪽은 왼쪽 트리, 오른쪽은 오른쪽 트리입니다.왼쪽 트리의 개수count를 구하고 앞의 서열에서 첫 번째 노드를 제외하고 다음의count 요소는 왼쪽 트리의 앞의 서열을 구성하고 나머지는 오른쪽 트리의 앞의 서열을 구성한다.
시작, 교체기를 사용하지 않았습니다. vector가 대량의 공간을 차지했음을 설명합니다. Memory Limit Exceeded...
코드:

/** * Definition for a binary tree node. * 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) {
        if (preorder.empty() && inorder.empty())
            return NULL;

        // 
        int size = preorder.size();

        // 
        TreeNode *root = new TreeNode(preorder[0]);

        int pos = 0;
        // 
        for (int i=0; i<size; ++i)
        {
            if (inorder[i] == preorder[0])
            {
                pos = i;
                break;
            }//if
        }//for

        if (pos >= 0 && pos < size)
        {
            // inOrder （0 ， pos-1） （pos+1，size-1） 
            // preOrder （1，pos） （pos+1,size-1） 
            vector<int> left_pre;
            for (int j = 1; j <= pos; j++)
                left_pre.push_back(preorder[j]);

            vector<int> left_in;
            for (int j = 0; j < pos; ++j)
                left_in.push_back(inorder[j]);

            root->left = buildTree(left_pre, left_in);

            // 
            vector<int> right_pre , right_in;
            for (int j = pos + 1; j < size; j++)
            {
                right_pre.push_back(preorder[j]);
                right_in.push_back(inorder[j]);
            }

            root->right = buildTree(right_pre, right_in);
        }
        return root;        
    }
};

그리고 교체기를 사용하여 불필요한 공간 사용을 피하고, AC~

AC 코드

class Solution {
public:

    template <typename Iter>
    TreeNode* make(Iter pre_begin, Iter pre_end, Iter in_begin, Iter in_end) {

        if (pre_begin == pre_end || in_begin == in_end)
            return NULL;

        // 
        TreeNode *root = new TreeNode(*pre_begin);

        // 
        Iter iter = find(in_begin, in_end, *pre_begin);

        int count = iter - in_begin;

        if (iter != in_end)
        {
            // inOrder （0 ， pos-1） （pos+1，size-1） 
            // preOrder （1，pos） （pos+1,size-1） 

            root->left = make(pre_begin + 1, pre_begin + count + 1, in_begin, iter);

            // 
            root->right = make(pre_begin + count + 1, pre_end, iter + 1, in_end);
        }
        return root;

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty())
            return NULL;

        return make(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

GitHub 테스트 프로그램 소스