앞 순서 중 순서 구축 두 갈래 트리

제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 재건하십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {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||vin.size() == 0)
            return NULL;

        TreeNode* root = new TreeNode(pre[0]);
        int len = vin.size();

        int firstroot = 0;
        while(vin[firstroot] != pre[0]) firstroot++;

        vector<int> pre_left,pre_right,vin_left,vin_right;

        for(int i=0;i// ,i+1 
            pre_left.push_back(pre[i+1]);
            // 
            vin_left.push_back(vin[i]);
        }
        for(int j=firstroot+1;j// 
        root->left = reConstructBinaryTree(pre_left,vin_left);
        root->right = reConstructBinaryTree(pre_right,vin_right);
        return root;
    }
};

좋은 웹페이지 즐겨찾기