검지 Offer_프로그래밍 문제

2140 단어
제목:
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
총 사고방식:
1. 우선 시퀀스에서 첫 번째 수치를 찾아 중간 시퀀스를 좌우 트리로 구분하고 순서대로 귀속한다.
2. 시퀀스에 한 개만 있을 때 노드를 만들고 이전 단계로 호출해서 되돌려줍니다.
지식 포인트(나에게):
1. 두 갈래 나무를 재구성하는 것은 익숙한 제목이지만, 원래는 수중에 여러 번 했을 뿐, OJ에서는 처음이어서 문제가 생겼다.
2. CodeBlocks에서 기본 디버깅 기술을 습득한다.
https://www.cnblogs.com/esCharacter/p/7927696.html
3.0,null,nullptr의 차이.
https://blog.csdn.net/fxbjye/article/details/77989569
4. 코드의 노봉성
여러 가지 오류 처리를 고려해야 합니다. 코드를 보십시오.
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:
    TreeNode* reConstructBinaryTree(vector pre,vector vin) {
        if(pre.empty()||vin.empty())
            return nullptr;
        return reConstruct(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    }
    TreeNode* reConstruct
    (
        vector pre, int preStart, int preEnd,
        vector vin, int vinStart, int vinEnd
    ){
        int rootValue = pre[preStart];
        TreeNode* root = new TreeNode(rootValue);
        if(preStart==preEnd){// 
            if(vinStart==vinEnd && pre[preStart]==vin[vinStart])
                //1. 
                //2. 
                return root;
            else
                throw "Invalid input";
        }
        // 
        // root 
        int rootInVin = vinStart;
        while(vin[rootInVin]!=rootValue && rootInVin0)
            root->left = reConstruct(pre, preStart + 1, leftPreEnd, vin, vinStart, rootInVin-1);
        if(leftLengthright = reConstruct(pre, leftPreEnd+1, preEnd, vin, rootInVin+1, vinEnd);
        return root;
    }
    
};

반응 7분
검지offer의 지그재그 순서로 두 갈래 나무 인쇄

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage