从前序与中序遍历序列构造二叉树

高刷题

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* track_back(vector<int>& preorder, vector<int>& inorder , int left_p , int right_p , int left_i , int right_i )
    {

        if(right_p < left_p || right_i < left_i 
            || left_p < 0 || left_i < 0 
            || right_p >= preorder.size() || right_i >= inorder.size()) return nullptr;

        TreeNode *node = new TreeNode(preorder[left_p]);
        if(left_p == right_p && left_i == right_i) return node;
        int tmp_i;
        for(int i=left_i ; i <= right_i ; i++)
        {
            if(inorder[i] == node->val)
            {
                tmp_i = i;
                break;
            }
        }

        int size_left = tmp_i - left_i;
        int size_right = right_i - tmp_i;
        cout<<node->val<<' '<<size_left<<' '<<size_right<<endl;
        node->left = track_back(preorder,inorder,
                                left_p+1,
                                left_p+1+size_left - 1,
                                left_i,
                                tmp_i -1 );

        node->right = track_back(preorder,inorder,
                                left_p+1+size_left,
                                right_p,
                                tmp_i+1,
                                right_i);


        return node;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return track_back(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
};