앞 순서에 따라 트리와 중간 순서에 따라 두 갈래 트리를 구성한다

1438 단어
앞의 순서에 따라 트리와 중간의 순서에 따라 두 갈래 트리를 구성한다.
예제
중차 역행 제시: [1,2,3] 과 전차 역행: [2,1,3].다음 트리로 돌아갑니다.
  2
 / \
1   3

트리에 같은 수치의 노드가 존재하지 않는다고 가정하다
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        int n=preorder.size();
        if(n==0) return NULL;
        return helper(preorder,0,n-1,inorder,0,n-1);
    }
    TreeNode* helper(vector<int>& preorder,int l1,int r1,vector<int>&inorder,int l2,int r2){
        if(l1>r1||l2>r2) return NULL;
        int i;
        for(i=l2;i<=r2;++i){
            if(inorder[i]==preorder[l1])
            break;
        }
        TreeNode *root=new TreeNode(preorder[l1]);
        root->left=helper(preorder,l1+1,l1+i-l2,inorder,l2,i-1);
        root->right=helper(preorder,l1+i-l2+1,r1,inorder,i+1,r2);
        return root;
    }
    
};

좋은 웹페이지 즐겨찾기