【剑指 Offer.07 重建二叉树】

递归方法

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

class Solution {
public:
    unordered_map<int, int> index;
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode *myBuildTree(vector<int> &preorder, vector<int> &inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        int root_pre_idx = preorder_left;
        TreeNode *root = new TreeNode(preorder[root_pre_idx]);
        int root_in_idx = index[preorder[root_pre_idx]];
        int left_tree_cnt = root_in_idx - inorder_left;
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + left_tree_cnt, inorder_left, root_in_idx - 1);
        root->right = myBuildTree(preorder, inorder, preorder_left + left_tree_cnt + 1, preorder_right, root_in_idx + 1, inorder_right);
        return root;
    }
};