LeetCode105. フロントシーケンスとミッドシーケンス遍歴シーケンスによるツリーの構築

トピック解析:前のシーケンスの最初のノードからツリーのルートノードを決定し、中シーケンスシーケンスでノードを見つけることができます.ノードの左側にあるのはルートノードの左サブツリーで、ノードの右側にあるのはルートノードの右サブツリーです.次に,左右のサブツリーノードの数に応じて,それぞれのサブツリーの前シーケンスを前シーケンスで知ることができる.左サブツリーノードの数が3であると仮定すると、前シーケンスの最初のノードを除いて、後の3つがその左サブツリーのノードの前シーケンスシーケンスであり、それに応じて、後のノードが右サブツリーノードの前シーケンスである.
preorder[pl.....pr]を前系列とし、inorder[i l.....ir]を対応する中系列として、絶えず再帰する.
コードの表示:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        return constructTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
    
    TreeNode* constructTree(vector& preorder,int pl,int pr,vector& inorder,int il,int ir){
        if(pl>pr || il>ir)
            return NULL;
        TreeNode* root = new TreeNode(preorder[pl]);
        for(int k=il;k<=ir;k++){
            if(preorder[pl]==inorder[k]){
                root->left = constructTree(preorder,pl+1,pl+k-il,inorder,il,k-1);
                root->right = constructTree(preorder,pl+k-il+1,pr,inorder,k+1,ir);
            }
        }
        return root;
    }
};