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

https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv7pir/

cost: 8m34s

/**
 * 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return this->buildTree_(preorder, 0, preorder.size() - 1, inorder, 0,
                                inorder.size() - 1);
    }

private:
    TreeNode* buildTree_(vector<int>& preorder, int i, int j,
                         vector<int>& inorder, int x, int y) {
        if (i > j) {
            return nullptr;
        }
        if (i == j) {
            return new TreeNode(preorder[i]);
        }
        auto node = new TreeNode(preorder[i]);
        for (int k = x; k <= y; k++) {
            if (inorder[k] != preorder[i]) {
                continue;
            }
            node->left = this->buildTree_(preorder, i + 1, i + (k - x), inorder,
                                          x, k - 1);
            node->right = this->buildTree_(preorder, i + 1 + (k - x), j,
                                           inorder, k + 1, y);
            break;
        }
        return node;
    }
};