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

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

补更，二叉树构造！！这个非常重要！！

分六部分：

// 1、后序数组为空，返回空节点

// 2、后序数组最后一个元素，为节点元素。数组大小为1，返回节点。

// 3、以上一节点元素作为切割点，寻找中序数组的位置

// 4、切割中序数组

// 5、切割后序数组

// 6、递归处理左右区间

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;
    }
};

46.全排列

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool>& used) {
        // 终止条件
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue;

            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
        return;
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }
};

47.全排列 II

多判断一个 同一层循环相邻重复元素的去重

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracking(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // 全排列，同位置跳过
            if ((i > 0 && nums[i-1] == nums[i] && used[i-1] == true)) continue; // 去重
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            used[i] = false;
            path.pop_back();
        }
        return;
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }
};