P123 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

[HelloYJohn]

    if (preorder.empty()) {
       return nullptr;
    }
    unordered_map<int, int> hash;
    for (int i = 0; i < preorder.size(); ++i) {
       hash[inorder[i]] = i;
    }
    return buildTreeHelper(hash, preorder, 0, preorder.size() - 1, 0);
}
// 辅函数
TreeNode* buildTreeHelper(unordered_map<int, int> & hash, vector<int>& preorder
    , int s0, int e0, int s1) {
    if (s0 > e0) {
       return nullptr;
    }
    int mid = preorder[s1], index = hash[mid], leftLen = index - s0 - 1;
    TreeNode* node = new TreeNode(mid);
    node->left = buildTreeHelper(hash, preorder, s0, index - 1, s1 + 1);
    node->right = buildTreeHelper(hash, preorder, index + 1, e0, s1 + 2 +
       leftLen);
    return node;
}

首先感谢作者，算法没问题，只是一些变量定义的出入 leftLen = index - s0 - 1;
应改为leftLen = index - s0 + 1; 后面用leftLen的时候 node->right = buildTreeHelper(hash, preorder, index + 1, e0, s1 + leftLen);

[changgyhub]

感谢！2.0版本会更正。