題目鏈接

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

代碼

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pi = 0;
        return dfs(preorder, pi, inorder, 0, inorder.size() - 1);
    }

    TreeNode* dfs(vector<int>& preorder, int &pi, vector<int>& inorder, int is, int it) {
        if (is > it) {
            return NULL;
        }
        int val = preorder[pi];
        TreeNode *parent = new TreeNode(val);
        int pos = is;
        while (pos <= it && val != inorder[pos]) {
            pos++;
        }
        pi++;
        parent->left = dfs(preorder, pi, inorder, is, pos - 1);
        parent->right = dfs(preorder, pi, inorder, pos + 1, it);
        return parent;
    }
};