두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 입력 전차 역행 시퀀스 {1,2,4,7,3,5,6,8}와 중차 역행 시퀀스 {4,7,2,1,5

8409 단어 검지offer
제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 재건하십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.사고방식:pre:12473568in:47215386 매번 앞 순서대로 흐르는 첫 번째 값을 추출한 다음에 중간 순서대로 이 값이 있는 아래 표를 찾으면 새 노드는 루트, 루트->left는 왼쪽으로 구성된 하위 트리, 루트->right는 오른쪽으로 구성된 하위 트리를 가리킨다.차례대로 돌아가다.코드:
 * 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) {
        TreeNode *root = reConstructBinaryTree(pre,0,pre.size()-1,vin,0,vin.size()-1);
        return root;
        
    }
private:
    TreeNode * reConstructBinaryTree(vector<int> pre, int pre_start,int pre_end,vector<int>vin,int vin_start,int vin_end){
    if(pre_start>pre_end || vin_start>vin_end){
        return NULL;
    }
    TreeNode  *root = new TreeNode(pre[pre_start]);
    for(int i=vin_start;i<=vin_end;i++){
        if(vin[i]==pre[pre_start]){
            root->left= reConstructBinaryTree(pre,pre_start+1,i-vin_start+pre_start,vin,vin_start,i-1);
            root->right= reConstructBinaryTree(pre,i-vin_start+pre_start+1,pre_end,vin,i+1,vin_end);
            break;
        }
    }
    return root;
    }
};

좋은 웹페이지 즐겨찾기