立志重刷代码随想录60天冲冲冲！！——第二十五天

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

这道题是之前二叉树没来得及写的，今天补上

class Solution {
public:
    // 1、后序数组为空，返回空节点
    // 2、后序数组最后一个元素，为节点元素
    // 3、以上一节点元素作为切割点，寻找中序数组的位置
    // 4、切割中序数组
    // 5、切割后序数组
    // 6、递归处理左右区间 
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL; // 终止条件
        int postValue = postorder.back();   // 后序最后一个元素
        TreeNode* node = new TreeNode(postValue); 
        if (postorder.size() == 1) return node; // 如果后序数组就剩一个元素，返回刚刚创建的节点
        
        int postIdx = 0;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder[i] == postValue) {
                postIdx = i;
                break;
            }
        }

        // 切割中序 (左闭右开)
        vector<int> Leftinorder(inorder.begin(), inorder.begin() + postIdx);
        vector<int> Rightinorder(inorder.begin() + postIdx + 1, inorder.end());
        // 切割后序 (左闭右开)
        vector<int> Leftpostorder(postorder.begin(), postorder.begin() + postIdx);
        vector<int> Rightpostorder(postorder.begin() + postIdx, postorder.end() - 1);

        node->left = buildTree(Leftinorder, Leftpostorder);
        node->right = buildTree(Rightinorder, Rightpostorder);

        return node;
    }
};

491.递增子序列

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIdx) {
        if (path.size() >= 2) {
            res.push_back(path);
            // 不要加return！！
        }

        unordered_set<int> uset;
        for (int i = startIdx; i < nums.size(); i++) {
            if ((!path.empty() && path.back() > nums[i]) 
                || uset.find(nums[i]) != uset.end()) continue;

            uset.insert(nums[i]); // 在一层中，不可以重复。但下一次递归会初始化，也相当于回溯
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }
};