LeetCode-- Construct Binary Tree from Preorder and Inorder Traversal

 
               8
             /   \
           6     7
          /     /
         4     5
          \   / \
           1  2  3

Preorder    : {8} 6 4 1 7 5 2 3  
Inorder     : 4 1 6 {8} 2 5 3 7  
PostOrder   : 1 4 6 2 3 5 7 {8} 

Preorder와 Inorder 또는 Postorder와 Inorder의 조합에서만 두 갈래 트리를 구성할 수 있습니다.
예를 들어 Preorder와 Inorder의 조합
첫 번째 단계: {8}를 뿌리로 나누어 {8}, {6 4 1}, {7 5 2 3}과 {4 1 6}, {8}, {2 5 3 7}로 나눈다.
두 번째 단계: 같은 이치로 왼쪽 {641}과 {416}를 뿌리로 구분한다.오른쪽 {7 5 2 3}과 {2 5 3 7}, {7}을 뿌리로 구분합니다.
…
최종적으로 단일 원소 집합까지 구분한다.

Construct Binary Tree from Preorder and Inorder Traversal

class Solution {
public:
    TreeNode* buildTree(vector<int> & preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end){

        if(pre_end<pre_start) return NULL;

        TreeNode *node = new TreeNode(preorder.at(pre_start));

        //if(pre_start==pre_end) return node;

        int i;
        for(i=0; i<inorder.size(); i++){
            if(node->val==inorder.at(in_start+i)){
                break;
            }
        }

        node->left = buildTree(preorder, inorder, pre_start+1, pre_start+i, in_start, in_start+i-1);
        node->right = buildTree(preorder, inorder, pre_start+i+1, pre_end, in_start+i+1, in_end);

        return node;
    }


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

        return buildTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size());
    }
};

Construct Binary Tree from Inorder and Postorder Traversal

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

        return buildTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int in_start, int in_end, int post_start, int post_end){
        if(post_end<post_start) return NULL;

        TreeNode* node = new TreeNode(postorder.at(post_end));

        //if(post_end=post_start) return node;

        int i;
        for(i=0; i<inorder.size(); i++){
            if (node->val == inorder.at(in_start+i)){
                break;
            }
        }

        node->left = buildTree(inorder, postorder, in_start, in_start+i-1, post_start, post_start+i-1);
        node->right = buildTree(inorder, postorder, in_start+i+1, in_end, post_start+i, post_end-1);

        return node;
    }
};