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

Problem: 106. 从中序与后序遍历序列构造二叉树

Reference

代码随想录 (programmercarl.com)

思路

不难,但是要理清楚顺序,还要确定切割区间，我们保持左闭右开的区间，因为vector也是左闭右开begin(),end()。

第1步：找到后序数组最后一个元素在中序数组的位置，作为切割点

第2步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

第3步：切割后序数组，按照中序切割后的大小，切成后序左数组和后序右数组，注意后序的最后一个元素不要postorder.end() - 1。

第4步：递归处理左区间和右区间

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
private:
    TreeNode* traversal(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.empty())
            return nullptr;
        // 找到后序最后一个元素
        int mid = postorder.back();
        // 生成节点
        TreeNode* node = new TreeNode(mid);
        // 找到他在中序中的位置
        int midIndex = 0;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder[i] == mid) {
                midIndex = i;
            }
        }
        // 切割中序
        vector<int> leftInorder(inorder.begin(), inorder.begin() + midIndex);
        vector<int> rightInorder(inorder.begin() + midIndex + 1, inorder.end());
        // 切割后序
        vector<int> leftPostorder(postorder.begin(),
                                  postorder.begin() + leftInorder.size());
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(),
                                   postorder.end() - 1);
        node->left = traversal(leftInorder, leftPostorder);
        node->right = traversal(rightInorder, rightPostorder);
        return node;
    }

public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        TreeNode* root = traversal(inorder, postorder);
        return root;
    }
};