LC-106-从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题面

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

• 中序遍历 inorder = [9,3,15,20,7]
• 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：

思路

TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
    if (postorder.size() == 0) return NULL;
    
    // 后序遍历数组最后一个元素，就是当前的中间节点
    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);
    
    // 叶子节点
    if (postorder.size() == 1) return root;
    
    // 找到中序遍历的切割点
    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++)
        if (inorder[delimiterIndex] == rootValue) break;
    
    // 切割中序数组
    // 左闭右开区间：[0, delimiterIndex)
    vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
    // [delimiterIndex + 1, end)
    vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
    
    // postorder舍弃末尾元素
    postorder.resize(postorder.size() - 1);
    
    // 切割后序数组
    // 依然左闭右开，注意这里使用了左中序数组大小作为切割点
    // [0, leftInorder.size]
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
    // [leftInorder.size, end]
    vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
    
    root->left = traversal(leftInorder, leftPostorder);
    root->right = traversal(leftPostorder, rightPostorder);
    
    return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.size() == 0 || postorder.size() == 0) return NULL;
    return traversal(inorder, postorder);
}