제목:

두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.
입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.
예를 들어 앞 순서 역행 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 역행 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 뒷 순서 역행 시퀀스를 출력합니다.
두 갈래 나무의 정의는 다음과 같다.

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

생각:

두 갈래 나무의 선차적 역행 서열에서 첫 번째 수는 항상 수의 뿌리 결점의 값이고 뒤는 왼쪽 나무 결점의 값, 오른쪽 나무 결점의 값이다.
두 갈래 나무의 중차순 역행 서열에서 뿌리 노드는 서열 중간에 있고 뿌리 노드는 왼쪽은 왼쪽 나무이고 오른쪽은 오른쪽 나무이다.
위의 정보에 따라 다음과 같은 작업을 수행할 수 있습니다.
먼저 루트 노드를 순서대로 훑어보고,
그리고 중차 반복 시퀀스에서 루트 노드를 찾으면 왼쪽 트리와 오른쪽 트리를 확인할 수 있습니다.
이어서 다시 순서대로 돌아가 시퀀스에서 왼쪽 트리와 오른쪽 트리를 찾아 상기 절차를 반복합니다 (귀속).

코드:

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

BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder){
    int rootValue=startPreorder[0];
    BinaryTreeNode* root=new BinaryTreeNode(rootValue);
    if(startPreorder==endPreorder && startInorder==endInorder)
        return root;
//    else
//        throw std::exception("Invalid Input.
");

    int* rootInorder=startInorder;
    while(rootInorder!=endInorder && *rootInorder!=rootValue)
        ++rootInorder;

//    if(rootInorder==endInorder && *rootInorder!=rootValue)
//        throw std::exception("Invalid Input.
");

    int leftLength=rootInorder-startInorder;
    int* leftPreOrderEnd=startPreorder+leftLength;
    if(leftLength>0)
        root->left=ConstructCore(startPreorder+1,leftPreOrderEnd,startInorder,rootInorder-1);
    int rightLength=endPreorder-startPreorder-leftLength;
    if(rightLength>0)
        root->right=ConstructCore(leftPreOrderEnd+1,endPreorder,rootInorder+1,endInorder);
    return root;
}

BinaryTreeNode* Construct(int* preOrder,int* inOrder,int length){
    if(preOrder==NULL || inOrder==NULL || length<=0)
        return NULL;
    return ConstructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1);
}

온라인 테스트 OJ:

http://www.nowcoder.com/books/coding-interviews/8a19cbe657394eeaac2f6ea9b0f6fcf6?rp=1
AC 코드:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    struct TreeNode* construct(const vector<int> &pre,int startPre,int endPre,const vector<int> &in,int startIn,int endIn){
        int rootValue=pre[startPre];
        TreeNode* root=new TreeNode(rootValue);
        if(startPre==endPre && startIn==endIn)
            return root;

        int rootIndex=startIn;
        while(rootIndex<=endIn && in[rootIndex]!=rootValue)
            rootIndex++;

        int leftLength=rootIndex-startIn;
        if(leftLength>0)
            root->left=construct(pre,startPre+1,startPre+leftLength,in,startIn,rootIndex-1);
		int rightLength=endPre-startPre-leftLength;
        if(rightLength>0)
            root->right=construct(pre,startPre+leftLength+1,endPre,in,rootIndex+1,endIn);

        return root;
    }

	struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
		int len=pre.size();
        if(len<=0)
            return NULL;
        return construct(pre,0,len-1,in,0,len-1);
	}
};