算法笔记

回溯算法思考步骤：

1. 绘制递归树，找到回溯算法的参数
2. 寻找回溯算法的结束条件
3. 确定选择列表，判断把什么数据填充到结果列表
4. 判断是否需要剪枝，即数据是否已经存储过
5. 递归调用函数，进入下一层
6. 撤销选择，回到上一层

二叉树的遍历

// 定义二叉树节点结构体
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

// 前序遍历（递归）
void preorder(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->value << " ";   // 访问根节点
    preorder(root->left);              // 遍历左子树
    preorder(root->right);             // 遍历右子树
}

// 中序遍历（递归）
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);               // 遍历左子树
    std::cout << root->value << " ";   // 访问根节点
    inorder(root->right);              // 遍历右子树
}

// 后序遍历（递归）
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);             // 遍历左子树
    postorder(root->right);            // 遍历右子树
    std::cout << root->value << " ";   // 访问根节点
}

// 层次遍历（递归）
// 层次遍历
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    std::queue<TreeNode*> q; // 使用队列存储节点
    q.push(root);             // 将根节点入队

    while (!q.empty()) {
        TreeNode* node = q.front();  // 获取队列头节点
        q.pop();                     // 将队列头节点出队
        std::cout << node->value << " ";  // 访问当前节点

        // 如果当前节点有左子树，入队左子树
        if (node->left) {
            q.push(node->left);
        }

        // 如果当前节点有右子树，入队右子树
        if (node->right) {
            q.push(node->right);
        }
    }
}

使用前序遍历和中序遍历重建二叉树

思路：

1. 前序的第一个节点是根节点
2. 中序中找到根的位置，左边是左子树，右边是右子树
3. 分别划分左右两侧，然后继续使用1,2准则构建

/ 使用前序遍历和中序遍历重建二叉树
TreeNode* buildTreeHelper(const std::vector<int>& preorder, int& preIndex,
                          const std::unordered_map<int, int>& inorderMap, int inStart, int inEnd) {
    // 基础条件：如果范围不合法，返回空
    if (inStart > inEnd) {
        return nullptr;
    }

    // 1. 获取当前根节点的值
    int rootValue = preorder[preIndex];
    TreeNode* root = new TreeNode(rootValue);

    // 2. 在中序遍历中找到根节点的位置
    int rootInIndex = inorderMap.at(rootValue);

    // 3. 增加前序遍历的索引
    preIndex++;

    // 4. 递归构建左子树和右子树
    root->left = buildTreeHelper(preorder, preIndex, inorderMap, inStart, rootInIndex - 1);
    root->right = buildTreeHelper(preorder, preIndex, inorderMap, rootInIndex + 1, inEnd);

    return root;
}

// 主函数：从前序遍历和中序遍历重建二叉树
TreeNode* buildTree(const std::vector<int>& preorder, const std::vector<int>& inorder) {
    // 1. 创建中序遍历的哈希表，快速查找根节点的位置
    std::unordered_map<int, int> inorderMap;
    for (int i = 0; i < inorder.size(); ++i) {
        inorderMap[inorder[i]] = i;
    }

    int preIndex = 0;  // 记录前序遍历的当前索引
    return buildTreeHelper(preorder, preIndex, inorderMap, 0, inorder.size() - 1);
}

快速排序算法

// 快速排序的划分操作
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择基准元素
    int i = low - 1;        // i 指向比基准小的区域的最后一个元素

    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {  // 如果当前元素小于基准元素
            i++;               // 增加 i 的值
            std::swap(arr[i], arr[j]);  // 将 arr[i] 和 arr[j] 交换
        }
    }
    // 将基准元素放到正确的位置
    std::swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回基准元素的索引
}

// 快速排序的主函数
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取划分的索引
        quickSort(arr, low, pi - 1);         // 对基准左侧部分进行递归排序
        quickSort(arr, pi + 1, high);        // 对基准右侧部分进行递归排序
    }
}