우객망 문제 해결 | 두 갈래 나무 재건

제목 출처: 우객망 프로그래밍 링크
제목 설명
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
문제 해결:
전차와 중차가 두루 다니는 결과는 유일하게 두 갈래 나무를 확정할 수 있지만, 전차와 후차가 유일하게 두 갈래 나무를 확정할 수 없다는 것을 안다.
앞의 순서를 이용하여 첫 번째 숫자를 뿌리로 하고 이 뿌리로 중간의 순서에서 찾으면 왼쪽은 왼쪽 나무, 오른쪽은 오른쪽 나무로 좌우의 길이를 계산하고 그 길이로 앞의 순서에서 좌우의 나무를 구분하여 상술한 과정을 반복하면 이 두 갈래 나무를 재건할 수 있다.
코드:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0)
        {
            return NULL;
        }     
        TreeNode *node = dfs(pre,vin,0,pre.size(),0,vin.size());
        return node;
    }

    TreeNode* dfs(vector<int>&pre,vector<int>&vin,int p_l,int p_r,int v_l,int v_r)
    {
        if(p_l == p_r)     // 
        {
            return NULL;
        }
        int pos = -1;   
        TreeNode* node = new TreeNode(pre[p_l]);   // 
        for(int i= v_l;iif(vin[i] == pre[p_l])
                pos = i;
        }       
        node->left = dfs(pre,vin,p_l+1,p_l+1+pos-v_l,v_l,pos);
        node->right = dfs(pre,vin,p_l+1+pos-v_l,p_r,pos+1,v_r);           
        return node;
    }
};

운행 시간: 4ms;사용 메모리: 612k