Top100（中）

二叉树

94. 二叉树的中序遍历

int *res;

void inorder(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    // 左根右
    inorder(root->left, returnSize);
    res[(*returnSize)++] = root->val;
    inorder(root->right, returnSize);
}

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    inorder(root, returnSize);
    return res;
}

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    struct TreeNode *stack[100];
    int top = 0;

    while (top != 0 || root != NULL) {
        // 左子树入栈
        while (root != NULL) {
            stack[top++] = root;
            root = root->left;
        }

        root = stack[--top];
        // 访问
        res[(*returnSize)++] = root->val;
        root = root->right;
    }

    return res;
}

int *res;

void inorderMorris(struct TreeNode *root, int *returnSize) {
    if (root == NULL) return;
    struct TreeNode *cur = root;
    while (cur != NULL) {
        if (cur->left != NULL) {
            struct TreeNode *rightMost = cur->left;
            while (rightMost->right != NULL && rightMost->right != cur) {
                rightMost = rightMost->right;
            }
            if (rightMost->right == NULL) {
                rightMost->right = cur;
                cur = cur->left;
            } else {
                // 有左右孩子的节点第二次被经过，左子树都遍历完了，访问节点
                res[(*returnSize)++] = cur->val;
                rightMost->right = NULL;
                cur = cur->right;
            }
        } else {
            // 只有右孩子的节点只会被经过一次，直接访问
            res[(*returnSize)++] = cur->val;
            cur = cur->right;
        }
    }
}

int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    res = (int *) malloc(sizeof(int) * 100);
    *returnSize = 0;
    if (root == NULL) return res;
    inorderMorris(root, returnSize);
    return res;
}

104. 二叉树的最大深度

// 递归
int maxDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return (left > right ? left : right) + 1;
}

// 层序遍历
int maxDepth(struct TreeNode *root) {
    if (root == NULL) return 0;
    int depth = 0;
    const int size = 5002;
    // 循环队列
    struct TreeNode *queue[size];
    int front = 0, rear = 0;
    queue[rear++] = root;

    while (front != rear) {
        int count = (rear - front + size) % size;
        // 一层加一次
        depth++;
        while (count-- > 0) {
            struct TreeNode *node = queue[(front++) % size];
            if (node->left != NULL) queue[(rear++) % size] = node->left;
            if (node->right != NULL) queue[(rear++) % size] = node->right;
        }
    }
    return depth;
}

226. 翻转二叉树

struct TreeNode *invertTree(struct TreeNode *root) {
    if (root == NULL) return root;
 
    struct TreeNode *left = invertTree(root->right);
    struct TreeNode *right = invertTree(root->left);
    root->left = left;
    root->right = right;
    return root;
}

101. 对称二叉树

// 递归
bool dfs(struct TreeNode *L, struct TreeNode *R) {
    if (L == NULL && R == NULL) return true;
    if (L == NULL || R == NULL || L->val != R->val) return false;
    return dfs(L->left, R->right) && dfs(L->right, R->left);
}
 
bool isSymmetric(struct TreeNode *root) {
    if (root == NULL) return true;
    return dfs(root->left, root->right);
}

// 迭代
bool isSymmetric(struct TreeNode *root) {
    if (root == NULL) return true;
    if (root->left == NULL && root->right == NULL) return true;
    if (root->left == NULL || root->right == NULL || root->left->val != root->right->val) return false;
 
    const int size = 1001;
    struct TreeNode *queue[size];
    int front = 0, rear = 0;
    // 左右孩子入队
    queue[rear++] = root->left;
    queue[rear++] = root->right;
 
    while (rear != front) {
        struct TreeNode *L = queue[(front++) % size];
        struct TreeNode *R = queue[(front++) % size];
        if (L == NULL && R == NULL) return true;
        if ((L == NULL || R == NULL)
            || (L->val != R->val)
            || (L->left == NULL && R->right != NULL)
            || (L->right == NULL && R->left != NULL)
            || (L->right == NULL && R->left != NULL)
            || (L->left == NULL && R->right != NULL))
            return false;
        if (L->left != NULL) {
            queue[(rear++) % size] = L->left;
            queue[(rear++) % size] = R->right;
        }
        if (L->right != NULL) {
            queue[(rear++) % size] = L->right;
            queue[(rear++) % size] = R->left;
        }
    }
    return true;
}

543. 二叉树的直径

int res;
// 求树高的同时记录最远距离
int height(struct TreeNode *root) {
    if (root == NULL)return 0;
    int left = height(root->left);
    int right = height(root->right);
    if (left + right > res) res = left + right;
    return (left > right ? left : right) + 1;
}
 
int diameterOfBinaryTree(struct TreeNode *root) {
    res = 0;
    height(root);
    return res;
}

102. 二叉树的层序遍历

int **levelOrder(struct TreeNode *root, int *returnSize, int **returnColumnSizes) {
    // 一层最多元素个数
    const int size = 1002;
    // 最多层数
    const int leverMax = 2000;

    // 返回的二维数组，第一维表示所在层，第二维表示该层的所有元素
    int **res = (int **) malloc(sizeof(int *) * leverMax);
    // 一维的维度（多少层）
    *returnSize = 0;
    // 每个二维的维度（每层多少元素）
    *returnColumnSizes = (int *) malloc(sizeof(int) * leverMax);
    if (root == NULL) return res;


    // 循环队列
    struct TreeNode *queue[size];
    int lever = 0;
    // 保存每层元素个数，下标就是所在层，从0开始
    int *columnSize = (int *) calloc(leverMax, sizeof(int));
    int front = 0, rear = 0;
    queue[rear++] = root;

    while (front != rear) {
        // 当前层元素数
        int count = (rear - front + size) % size;
        res[lever] = (int *) malloc(sizeof(int) * count);
        int temp = 0;
        while (count-- > 0) {
            root = queue[(front++) % size];
            // 记录当前层的元素
            res[lever][temp++] = root->val;
            // 当前层元素总数加一
            columnSize[lever]++;
            if (root->left != NULL) queue[(rear++) % size] = root->left;
            if (root->right != NULL) queue[(rear++) % size] = root->right;
        }
        // 加一层
        lever++;
    }

    *returnSize = lever;
    for (int i = 0; i < lever; ++i) 
        (*returnColumnSizes)[i] = columnSize[i];
    return res;
}

108. 将有序数组转换为二叉搜索树

// 递归生成
struct TreeNode *generate(int *nums, int left, int right) {
    if (left > right) return NULL;
    // 向下取整的中间元素
    int mid = (right - left) / 2 + left;
    
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    node->val = nums[mid];
    node->left = generate(nums, left, mid - 1);
    node->right = generate(nums, mid + 1, right);
    return node;
}

98. 验证二叉搜索树

// 中序遍历
bool inorder(struct TreeNode *root) {
    if (root == NULL) return true;
    // 左
    if (!inorder(root->left)) return false;
    // 根
    if (pre != NULL && pre->val >= root->val) return false;
    pre = root;
    // 右
    return inorder(root->right);
}

bool isValidBST(struct TreeNode *root) {
    pre = NULL;
    return inorder(root);
}

// 判断子树是否在min到max的开区间内
bool dfs(struct TreeNode *root, long long min, long long max) {
    if (root == NULL) return true;
    if (root->val <= min || root->val >= max)return false;
    return dfs(root->left, min, root->val) && dfs(root->right, root->val, max);
}

bool isValidBST(struct TreeNode *root) {
    return dfs(root, 0x8000000000000000, 0x7fffffffffffffff);
}

230. 二叉搜索树中第K小的元素

199. 二叉树的右视图

int *rightSideView(struct TreeNode *root, int *returnSize) {
    *returnSize = 0;
    if (root == NULL) return NULL;
    int *res = (int *) malloc(sizeof(int) * 100);

    const int size = 52;
    struct TreeNode **queue = (struct TreeNode **) malloc(sizeof(struct TreeNode *) * size);
    int front = 0, rear = 0;
    queue[rear++] = root;

    // 层序遍历找一层的最后一个节点
    while (rear != front) {
        int count = (rear - front + size) % size;
        struct TreeNode *node;
        while (count-- > 0) {
            node = queue[(front++) % size];
            if (node->left != NULL) queue[(rear++) % size] = node->left;
            if (node->right != NULL) queue[(rear++) % size] = node->right;
        }
        res[(*returnSize)++] = node->val;
    }

    return res;
}

int *res;
int size;

void dfs(struct TreeNode *root, int depth, int *returnSize) {
    if (root == NULL) return;
    // 根
    if (depth == size) {
        // 如果是新的一层的第一个节点，就加入到结果中
        // 由于是根右左顺序，新一层的第一个节点一定是该层最右边的节点
        res[(*returnSize)++] = root->val;
        size++;
    }
    // 右
    dfs(root->right, depth + 1, returnSize);
    // 左
    dfs(root->left, depth + 1, returnSize);
}

int *rightSideView(struct TreeNode *root, int *returnSize) {
    *returnSize = 0;
    if (root == NULL) return NULL;
    res = (int *) malloc(sizeof(int) * 100);
    size = 0;
    dfs(root, 0, returnSize);
    return res;
}

114. 二叉树展开为链表

// 保存左右子树到栈中，再修改左右指针
void flatten(struct TreeNode *root) {
    if (root == NULL) return;
    struct TreeNode *stack[2000];
    int top = 0;
    struct TreeNode *temp, *pre = NULL;
    stack[top++] = root;

    while (top != 0) {
        root = stack[--top];
        temp = root;
        // 先压右，后压左
        if (root->right != NULL) stack[top++] = root->right;
        if (root->left != NULL) stack[top++] = root->left;

        temp->left = NULL;
        if (pre != NULL) pre->right = temp;
        pre = temp;
    }
}

// todo
// 神似morris
void flatten(struct TreeNode *root) {
    while (root != NULL) {
        if (root->left != NULL) {
            struct TreeNode *rightMost = root->left;
            while (rightMost->right != NULL)
                rightMost = rightMost->right;
            // 把右子树接到左子树的最右边的节点上
            rightMost->right = root->right;
            // 把追加过的左子树移到右子树的位置
            // 下一步访问的其实还是左节点，保证了先序
            root->right = root->left;
            root->left = NULL;
        }
        root = root->right;
    }
}

struct TreeNode *pre;

// 先序序列倒过来访问的递归写法（后序遍历递归写法的改写）
void dfs(struct TreeNode *root) {
    if (root == NULL) return;
    dfs(root->right);
    dfs(root->left);
    root->left = NULL;
    root->right = pre;
    pre = root;
}

void flatten(struct TreeNode *root) {
    pre = NULL;
    dfs(root);
}

// 先序序列倒过来访问的迭代写法（后序遍历迭代写法的改写）
void flatten(struct TreeNode *root) {
    if (root == NULL) return;
    struct TreeNode *stack[2000];
    int top = 0;
    struct TreeNode *pre = NULL;

    while (top != 0 || root != NULL) {
        while (root != NULL) {
            stack[top++] = root;
            root = root->right;
        }

        root = stack[--top];
        if (root->left != NULL && pre != root->left) {
            // 左子树不空且未被访问过
            stack[top++] = root;
            root = root->left;
        } else {
            // 左子树已经访问，可以处理当前节点
            root->left = NULL;
            root->right = pre;
            pre = root;
            root = NULL;
        }
    }
}

// 保存先序遍历的节点，再遍历一遍节点并同时修改

105. 从前序与中序遍历序列构造二叉树

// 递归
struct TreeNode *generate(int *preorder, int start, int preorderSize, int *inorder, int left, int right) {
    if (start > preorderSize || left > right) return NULL;
    struct TreeNode *root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    // start是前序遍历中当前正在处理的节点
    root->val = preorder[start];

    // todo 可以用散列快速定位
    // 定位root在中序遍历中的位置，left到pos-1的元素用于构造左子树，pos+1到right的元素用于构造右子树
    int pos = left;
    for (int i = left; i <= right; ++i) {
        if (inorder[i] == preorder[start]) {
            pos = i;
            break;
        }
    }

    // 先序: {preorder[start]}
    //      {左子树（一共leftCount个元素）}
    //      {右子树，第一个元素为preorder[start+1+leftCount]}
    // 中序: {left到pos-1（一共leftCount个元素），用于构造左子树}
    //      {preorder[start]也就是inorder[pos]}
    //      {pos+1到right用于构造右子树}

    // 左子树元素个数
    int leftCount = pos - left;
    // 构造左子树，左子树第一个节点的值是preorder[start+1]
    root->left = generate(preorder, start + 1, preorderSize, inorder, left, pos - 1);
    // 构造右子树，右子树第一个节点的值是preorder[start+1+leftCount]
    // 因为前序遍历中的start+1到start+leftCount一共leftCount个元素是用来构造左子树的
    root->right = generate(preorder, start + 1 + leftCount, preorderSize, inorder, pos + 1, right);
    return root;
}

struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
    return generate(preorder, 0, preorderSize, inorder, 0, inorderSize - 1);
}

// todo 看不懂
int pre;
int in;

struct TreeNode *generate(int *preorder, int preorderSize, int *inorder, int inorderSize, int stop) {
    if (pre == preorderSize) return NULL;
    if (inorder[in] == stop) {
        in++;
        return NULL;
    }
    int rootVal = preorder[pre++];
    struct TreeNode *root = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    root->val = rootVal;
    root->left = generate(preorder, preorderSize, inorder, inorderSize, rootVal);
    root->right = generate(preorder, preorderSize, inorder, inorderSize, stop);
    return root;
}

struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
    pre = 0;
    in = 0;
    return generate(preorder, preorderSize, inorder, inorderSize, 0x7fffffff);
}

// todo 迭代
struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
    if (preorderSize == 0) return NULL;
    struct TreeNode **stack = (struct TreeNode **) malloc(sizeof(struct TreeNode *) * 3000);
    int top = 0;

    int pre = 0;
    int in = 0;

    // 先序遍历的第一个值作为根节点
    struct TreeNode *curRoot = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    curRoot->val = preorder[pre++];
    curRoot->left = NULL;
    curRoot->right = NULL;
    stack[top++] = curRoot;
    // 作为最终根节点返回
    struct TreeNode *root = curRoot;

    // 遍历前序遍历的数组
    while (pre < preorderSize) {
        // 出现了当前节点的值和中序遍历数组的值相等，寻找是谁的右子树
        if (curRoot->val == inorder[in]) {
            // 每次进行出栈，实现倒着遍历
            while (top != 0 && stack[top - 1]->val == inorder[in]) {
                curRoot = stack[--top];
                in++;
            }
            // 设为当前的右孩子
            struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
            node->val = preorder[pre++];
            node->left = NULL;
            node->right = NULL;
            curRoot->right = node;
            curRoot = curRoot->right;
            stack[top++] = curRoot;
        } else {
            // 否则 作为左子树
            struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
            node->val = preorder[pre++];
            node->left = NULL;
            node->right = NULL;
            curRoot->left = node;
            curRoot = curRoot->left;
            stack[top++] = curRoot;
        }
    }
    return root;
}

437. 路径总和 III

// 返回从root开始往下的路径中和为targetSum的情况总数
int dfsCount(struct TreeNode *root, int targetSum, long long tempSum) {
    if (root == NULL) return 0;
    int tempRes = 0;
    tempSum += root->val;
    if (tempSum == targetSum) tempRes++;
    tempRes += dfsCount(root->left, targetSum, tempSum);
    tempRes += dfsCount(root->right, targetSum, tempSum);
    return tempRes;
}

// 累加从每个节点出发的情况总数
int dfs(struct TreeNode *root, long long targetSum) {
    if (root == NULL) return 0;
    return dfsCount(root, targetSum, 0) + dfs(root->left, targetSum) + dfs(root->right, targetSum);
}

// 暴力递归
int pathSum(struct TreeNode *root, int targetSum) {
    return dfs(root, targetSum);
}

// java版暴力递归
class Solution {
    int dfsCount(TreeNode root, int targetSum, long tempSum) {
        if (root == null) return 0;
        int tempRes = 0;
        tempSum += root.val;
        if (tempSum == targetSum) tempRes++;
        tempRes += dfsCount(root.left, targetSum, tempSum);
        tempRes += dfsCount(root.right, targetSum, tempSum);
        return tempRes;
    }

    int dfs(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return dfsCount(root, targetSum, 0) + dfs(root.left, targetSum) + dfs(root.right, targetSum);
    }

    public int pathSum(TreeNode root, int targetSum) {
        return dfs(root, targetSum);
    }
}

// todo *树的前缀和+回溯
class Solution {
    // 保存前缀树，key为前缀和，value为前缀和出现的次数
    Map<Long, Integer> hashMap = new HashMap<Long, Integer>();

    public int pathSum(TreeNode root, int targetSum) {
        // 前缀树为0的个数至少是一个
        hashMap.put(0L, 1);
        return dfs(root, 0, targetSum);
    }

    public int dfs(TreeNode root, long prefixSum, int targetSum) {
        if (root == null) return 0;
        // 计算前缀和
        prefixSum += root.val;
        // 若是存在前缀和为prefixSum - target的节点，则该节点到当前节点的路径就是符合题意的
        int cur = hashMap.getOrDefault(prefixSum - targetSum, 0);
        // 保存前缀和
        hashMap.put(prefixSum, hashMap.getOrDefault(prefixSum, 0) + 1);
        // 计算左右子树符合题意的个数
        int left = dfs(root.left, prefixSum, targetSum);
        int right = dfs(root.right, prefixSum, targetSum);
        // 从map中去掉当前节点的前缀和，使得兄弟结点无法使用当前结点的前缀和
        hashMap.put(prefixSum, hashMap.get(prefixSum) - 1);
        return cur + left + right;
    }
}

236. 二叉树的最近公共祖先

// 前提：节点的值唯一，p、q都在二叉树中
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){
    if(root == NULL)
        // 如果树为空，直接返回null
        return NULL;
    if(root == p || root == q)
        // 如果p和q中有等于root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
        return root;
    // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
    struct TreeNode *left = lowestCommonAncestor(root->left, p, q);
    // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
    struct TreeNode *right = lowestCommonAncestor(root->right, p, q);
    if(left == NULL)
        // 如果在左子树中p和q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        return right;
    else if(right == NULL)
        // 否则，如果left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况。如果在右子树中，p和q都找不到，则p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        return left;
    else
        //否则，当left和right均不为空时，说明p、q节点分别在 root异侧, 最近公共祖先即为 root
        return root;
}

// 方法二：记录跟节点到p、q的路径。从p、q往上找到第一个公共的节点

124. 二叉树中的最大路径和

图

200. 岛屿数量

994. 腐烂的橘子

207. 课程表

208. 实现 Trie (前缀树)

回溯

46. 全排列

int **res;
int *hashMap;
int *rtSize;

// temp中0到curIndex已经放入数据，现在往curIndex处放入所有可能
void generate(int *nums, int numsSize, int *temp, int curIndex) {
    // temp已经放满，把当前排列添加到结果中
    if (curIndex == numsSize) {
        for (int i = 0; i < numsSize; ++i) {
            res[(*rtSize)][i] = temp[i];
        }
        (*rtSize)++;
        return;
    }

    for (int i = 0; i < numsSize; ++i) {
        // nums[i]还没放入，就放入到curIndex位置
        if (hashMap[nums[i] + 10] == 0) {
            temp[curIndex] = nums[i];
            // 标记nums[i]已经放入
            hashMap[nums[i] + 10] = 1;
            // 递归处理子问题，尝试curIndex+1处所有的放入可能
            generate(nums, numsSize, temp, curIndex + 1);
            // 取消标记，再尝试在curIndex处放入其他还没使用过的数据
            hashMap[nums[i] + 10] = 0;
        }
    }
}

// 按字典序输出
int **permute(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    // 最多的组合数
    const int maxSize = 720;
    *returnSize = 0;
    res = (int **) malloc(sizeof(int *) * maxSize);
    *returnColumnSizes = (int *) malloc(sizeof(int) * maxSize);
    for (int i = 0; i < 720; ++i) {
        res[i] = (int *) malloc(sizeof(int) * numsSize);
        (*returnColumnSizes)[i] = numsSize;
    }

    rtSize = returnSize;
    // 标记数据是否已经使用过（即放入temp数组）
    hashMap = (int *) calloc(21, sizeof(int));
    // 暂存当前的排列
    int *temp = (int *) malloc(sizeof(int) * numsSize);
    
    generate(nums, numsSize, temp, 0);

    return res;
}

int **res;
int *rtSize;

void swap(int *array, int left, int right) {
    if (left == right) return;
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

// temp中0到curIndex已经放入数据，现在往curIndex处放入所有可能
void generate(int *nums, int numsSize, int *temp, int curIndex) {
    // temp已经放满，把当前排列添加到结果中
    if (curIndex == numsSize) {
        for (int i = 0; i < numsSize; ++i) {
            res[(*rtSize)][i] = temp[i];
        }
        (*rtSize)++;
        return;
    }

    // nums[left]开始到末尾都是尚未使用过的元素，从中挑出一个使用，并且在nums中和nums[left]交换位置
    // 这样以来nums从开头到nums[left]就是已经使用过的元素
    int left = curIndex;
    for (int right = left; right < numsSize; ++right) {
        temp[curIndex] = nums[right];
        // 标记nums[i]已经放入
        swap(nums, left, right);
        // 递归处理子问题，尝试curIndex+1处所有的放入可能
        generate(nums, numsSize, temp, curIndex + 1);
        // 取消标记，再尝试在curIndex处放入其他还没使用过的数据
        swap(nums, left, right);
    }
}

// 不按字典序输出，不使用hashMap标记元素是否使用过
int **permute(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    // 最多的组合数
    const int maxSize = 720;
    *returnSize = 0;
    res = (int **) malloc(sizeof(int *) * maxSize);
    *returnColumnSizes = (int *) malloc(sizeof(int) * maxSize);
    for (int i = 0; i < 720; ++i) {
        res[i] = (int *) malloc(sizeof(int) * numsSize);
        (*returnColumnSizes)[i] = numsSize;
    }

    rtSize = returnSize;
    // 暂存当前的排列
    int *temp = (int *) malloc(sizeof(int) * numsSize);

    generate(nums, numsSize, temp, 0);

    return res;
}

78. 子集

int **res;
int *rtSize;
int **rtColumnSize;

void generate(int *nums, int numsSize, int *temp, int len, int curIndex, int nextStart) {
    if (curIndex == len) {
        // 将长度为len的子集加入结果
        res[*rtSize] = (int *) malloc(sizeof(int) * len);
        (*rtColumnSize)[*rtSize] = len;
        for (int i = 0; i < len; ++i)
            res[*rtSize][i] = temp[i];
        (*rtSize)++;
        return;
    }

    // 当前位置选nums[i]，那么后面位置选的元素是从nums[i+1]开始选择的，避免选重复了
    // nextStart之前的已经被考虑过了
    for (int i = nextStart; i < numsSize; ++i) {
        // 从curIndex到结尾挑一个放在curIndex
        temp[curIndex] = nums[i];
        // 在curIndex已经放入nums[i]的条件下，考虑curIndex+1放入i后面的元素中的哪一个
        generate(nums, numsSize, temp, len, curIndex + 1, i + 1);
    }
}

int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    const int maxSize = 1024;
    res = (int **) malloc(sizeof(int *) * maxSize);
    rtSize = returnSize;
    *rtSize = 0;
    rtColumnSize = returnColumnSizes;
    *rtColumnSize = (int *) malloc(sizeof(int) * maxSize);
    int *temp = (int *) malloc(sizeof(int) * numsSize);

    res[0] = NULL;
    (*rtColumnSize)[0] = 0;
    (*rtSize)++;

    // 生成的长度逐渐加一
    for (int len = 1; len <= numsSize; ++len)
        generate(nums, numsSize, temp, len, 0, 0);
    return res;
}

// todo 01序列表示对应位置的元素是否选中
int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    int **res = (int **) malloc(sizeof(int *) * (1 << numsSize));
    *returnColumnSizes = (int *) malloc(sizeof(int) * (1 << numsSize));
    *returnSize = 1 << numsSize;

    int temp[numsSize];
    // mask中1的个数代表了子集中元素个数
    for (int mask = 0; mask < (1 << numsSize); ++mask) {
        // 记录子集中元素个数
        int len = 0;
        for (int i = 0; i < numsSize; ++i) {
            // 根据mask中1的位置判断nums[i]是否被选中
            // mask & (1 << i) != 0 说明被选中了
            if (mask & (1 << i)) {
                temp[len++] = nums[i];
            }
        }
        int *tempRes = (int *) malloc(sizeof(int) * len);
        memcpy(tempRes, temp, sizeof(int) * len);
        (*returnColumnSizes)[mask] = len;
        res[mask] = tempRes;
    }
    return res;
}

int **res;
int *rtSize;
int **rtColumnSize;

void generate(int *nums, int numsSize, int *temp, int len, int cur) {
    // cur==numsSize为true时，表示temp中已经在长度为len的情况下，已经尝试放过所有的元素
    if (cur == numsSize) {
        int *tempRes = (int *) malloc(sizeof(int) * len);
        memcpy(tempRes, temp, sizeof(int) * len);
        (*rtColumnSize)[*rtSize] = len;
        res[*rtSize] = tempRes;
        (*rtSize)++;
        return;
    }
    // 1.在temp[len]处放nums[cur]，然后考虑在temp[len+1]处放nums数组中从cur+1到结尾中的哪个元素
    temp[len] = nums[cur];
    generate(nums, numsSize, temp, len + 1, cur + 1);
    // 2.不在temp[len]处放nums[cur]，而是考虑在temp[len]处放nums数组中从cur+1到结尾中的哪个元素
    generate(nums, numsSize, temp, len, cur + 1);
}

int **subsets(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
    res = (int **) malloc(sizeof(int *) * (1 << numsSize));
    rtSize = returnSize;
    *rtSize = 0;
    rtColumnSize = returnColumnSizes;
    *rtColumnSize = (int *) malloc(sizeof(int) * (1 << numsSize));

    int *temp = (int *) malloc(sizeof(int) * numsSize);

    generate(nums, numsSize, temp, 0, 0);
    return res;
}

17. 电话号码的字母组合

39. 组合总和

22. 括号生成

79. 单词搜索

131. 分割回文串

51. N 皇后

二分查找

35. 搜索插入位置

// 左边界（大于等于target的第一个位置）
int searchInsert(int *nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (nums[mid] >= target)
            // 往左
            right = mid - 1;
        else
            // 往右
            left = mid + 1;
    }
    // 结束时，left=right+1
    // right右边全都大于等于target，left左边全都小于target
    return left;
}

74. 搜索二维矩阵

34. 在排序数组中查找元素的第一个和最后一个位置

// 左边界
int binarySearch1(int *array, int size, int target) {
    int left = 0, right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 右边界
int binarySearch2(int *array, int size, int target) {
    int left = 0, right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right;
}

int *searchRange(int *nums, int numsSize, int target, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 2;
    int left = binarySearch1(nums, numsSize, target);
    int right = binarySearch2(nums, numsSize, target);
    if (left >= numsSize || nums[left] != target) {
        res[0] = -1;
        res[1] = -1;
    } else {
        res[0] = left;
        res[1] = right;
    }
    return res;
}

33. 搜索旋转排序数组

153. 寻找旋转排序数组中的最小值

4. 寻找两个正序数组的中位数