BLOG

Record, summarize, and improve.
2026-08-16
Language

数据结构 & 算法

递归（recurion） 回溯算法（backtracking） 树

递归（recurion）

回溯算法（backtracking）

求组合问题模板 

		vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int index, int sum, vector<bool>& use) {
        if (sum > target)
            return;
        if (sum == target) {
            ans.push_back(path);
            return;
        }
        for ( ; index < candidates.size(); ++index) {
            if (index>0 && candidates[index] == candidates[index-1] && use[index-1] == false)
                continue;
            use[index] = true;
            path.push_back(candidates[index]);
            backtracking(candidates, target, index+1, sum+candidates[index], use);
            use[index] = false;
            path.pop_back();
        }
		}

求排列问题模板 

		vector<vector<int>> ans;
    vector<int> path;
    void backtracking(vector<int>& nums, int index, vector<bool>& used) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }
        for ( ; index < nums.size(); ++index) {
            if (used[index] == true)
                continue;
            path.push_back(nums[index]);
            used[index] = true;
            backtracking(nums, 0, used);
            path.pop_back();
            used[index] = false;
        }
    }

树

树的遍历：

  • 深度优先：

    前序遍历：根结点 ---> 左子树 ---> 右子树

    中序遍历：左子树---> 根结点 ---> 右子树

    后序遍历：左子树 ---> 右子树 ---> 根结点

  • 广度优先：按层次从左到右

二叉搜索树（BST）：左子树比父节点小，右节点比父节点大

哈希树（Hash）：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等，

前缀树或字典树（Trie）：根节点不包含字符，除根节点外每一个节点都只包含一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串

基数树（Radix）：与字典树机制相似，基数树是将key按指针地址bit位拆分，而字典树是将key的字符串值按字符拆分

平衡二叉树（AVL）：左右子树的高度相差不超过 1 的树为平衡二叉树

B树：平衡多路查找树（查找路径不只两个）

B+树：中间节点只用来索引，不保存数据

红黑树（自平衡二叉查找树）：根是黑色，所有叶子都是黑色，每个红色节点必须有两个黑色的子节点，从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

Language