算法 - 二叉树 / 图

🍺 二叉树

🍻 搜索树

🥂 96. 不同的二叉搜索树 [搜索树] [种类] (递归)

题解：

// 左子树有 left_num 种排列, 右子树有 right_num 种排列
// 以该节点为起点的排列种类共为 left_num * right_num
class Solution {
private:
    vector<vector<int>> dp;		// dp[i][j] 代表 nums[i...j] 可以构成的二叉搜索树类别数
public:
    int numTrees(int n) {
        dp.resize(n + 1, vector<int>(n + 1));
        return traverse(1, n);
    }
	// 递归, 先找 left_num, 再找 right_num, return left_num * right_num

    int traverse(int left, int right) {
        if (left >= right) return 1;
        if (dp[left][right] != 0) {		// 查询备忘录
            return dp[left][right];
        }
        int res = 0;					// 遍历计算种类, 轮流每个节点都当 root 节点
        for (int i = left; i <= right; ++i) {
            int left_num = traverse(left, i - 1);
            int right_num = traverse(i + 1, right);
            res += left_num * right_num;
        }
        dp[left][right] = res;			// 更新备忘录
        return res;
    }
};

🍻 栈

🥂 94. 二叉树的中序遍历 [二叉树] [遍历] (栈) (迭代)

class Solution {
private:
    stack<TreeNode*> stk;       // 存放已遍历节点
    vector<int> res;            // 存放结果
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        // 把左边节点都放进去
        TreeNode* tmp = root;
        while (tmp != nullptr) {
            stk.push(tmp);
            tmp = tmp->left;
        }
        // 开始遍历
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            // 把右节点的左节点方向全加进去
            if (cur->right != nullptr) {
                TreeNode* tmp = cur->right;
                while (tmp != nullptr) {
                    stk.push(tmp);
                    tmp = tmp->left;
                }
            }
        }
        return res;
    }
};

🥂 144. 二叉树的前序遍历 [二叉树] [遍历] (栈) (迭代)

class Solution {
private:
    stack<TreeNode*> stk;       // 存放已遍历节点
    vector<int> res;            // 存放结果
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        stk.push(root);
        // 开始遍历
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            stk.pop();
            res.push_back(cur->val);
            // 添加子节点, 先右再左
            if (cur->right != nullptr) stk.push(cur->right);
            if (cur->left != nullptr) stk.push(cur->left);
        }
        return res;
    }
};

🥂 145. 二叉树的后序遍历 [二叉树] [遍历] (栈) (迭代)

class Solution {
private:
    stack<TreeNode*> stk;       // 存放已遍历节点
    vector<int> res;            // 存放结果
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};
        stk.push(root);
        // 开始遍历
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            stk.pop();
            // 加入 res 中
            res.push_back(cur->val);
            // 开始加入子节点
            if (cur->left != nullptr) stk.push(cur->left);
            if (cur->right != nullptr) stk.push(cur->right);
        }
        // 将栈中元素反转就是答案
        reverse(res.begin(), res.end());
        return res;
    }
};

🍺 图

🍻 并查集

🥂 130. 被围绕的区域 [矩阵] [岛屿] (并查集)

class UF {
private:
    vector<int> parent;     // 某个节点的父节点
public:
    UF(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_(int p, int q) {
        int rootp = find(p), rootq = find(q);
        if (rootp != rootq) {
            parent[rootp] = rootq;
        }
    }
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
};

class Solution {
private:
    vector<vector<int>> dirts = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  // dfs 常用的上下左右
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty()) return;
        int m = board.size();
        int n = board[0].size();
        // 定义并查集
        UF uf(m * n + 1);
        int dummy = m * n;
        // 左右两列
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') {
                uf.union_(i * n, dummy);
            }
            if (board[i][n - 1] == 'O') {
                uf.union_((i + 1) * n - 1, dummy);
            }
        }
        // 上下两列
        for (int i = 0; i < n; ++i) {
            if (board[0][i] == 'O') {
                uf.union_(i, dummy);
            }
            if (board[m - 1][i] == 'O') {
                uf.union_(n * (m - 1) + i, dummy);
            }
        }
        // 将节点归类
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (board[i][j] == 'O') {
                    for (auto dirt : dirts) {
                        int x = i + dirt[0];
                        int y = j + dirt[1];
                        if (board[x][y] == 'O') {
                            uf.union_(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }
        // 将所有不与 dummy 相邻的节点都2置为 'X'
        for (int i = 1; i < m - 1; ++i) {
            for (int j = 1; j < n - 1; ++j) {
                if (!uf.connected(dummy, i * n + j)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
};

🥂 261. 以图判树 [图] [树] [环] (并查集)

class UF {
private:
    vector<int> parent;
    int count;
public:
    UF (int n) {
        count = n;
        for (int i = 0; i < n; ++i) parent.push_back(i);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_(int p, int q) {
        int rootp = find(p), rootq = find(q);
        if (rootp != rootq) {
            parent[rootp] = rootq;
            count--;
        }
    }
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
    int count_() {
        return count;
    }
};

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        UF uf(n);
        for (auto edge : edges) {
            int p = edge[0];
            int q = edge[1];
            // 如果新加入的边的两端, 处于同一个连通分量, 则会构成环
            if (uf.connected(p, q)) {
                return false;
            }
            uf.union_(p, q);
        }
        return uf.count_() == 1;
    }
};

🥂 305. 岛屿数量Ⅱ [矩阵] [岛屿] (并查集) (从0增加count)

class UF {
private:
    int count = 0;          // 连通分量
    vector<int> parent; // 元素 i 对应的父节点
public:
    UF(int n) {
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
        }
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_(int p, int q) {
        int rootp = find(p), rootq = find(q);
        if (rootp != rootq) {
            parent[rootp] = rootq;
            count--;
        }
    }
    bool isConnect(int p, int q) {
        return find(p) == find(q);
    }
    int count_() {
        return count;
    }
    void addCount() {
        count++;
    }
};

class Solution {
private:
    vector<int> res;        // 每一步添加后, 一共有多少个岛屿
    vector<int> grid;       // 岛屿
    vector<vector<int>> dirts = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};     // 方向
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        int size = positions.size();
        grid = vector<int>(m * n, 0);
        // 初始化并查集
        UF uf (m * n);
        // 开始一个个遍历节点
        for (auto& pos : positions) {
            int idx = pos[0] * n + pos[1];
            // 将水改为陆地
            if (grid[idx] == 0) {
                grid[idx] = 1;
                uf.addCount();
                // 开始和相邻节点合并
                for (auto& dirt : dirts) {
                    int newX = pos[0] + dirt[0];
                    int newY = pos[1] + dirt[1];
                    int newIdx = newX * n + newY;
                    // 和相邻节点没有连通, 那就连通, count--(函数内)
                    if (isArea(newX, newY, m, n) && grid[newIdx] == 1 && !uf.isConnect(idx, newIdx)) {
                        uf.union_(idx, newIdx);
                    }
                }
            }
            res.push_back(uf.count_());
        }
        return res;
    }
    // 是否越界
    bool isArea(int x, int y, int m, int n) {
        return (x >= 0 && y >= 0 && x < m && y < n);
    }
};

🥂 323. 无向图中连通分量的数目 [图] [连通分量] (并查集)

class UF {
private:
    int count = 0;      // 连通分量
    vector<int> parent; // 存储每个节点的父节点
public:
    UF(int n) {
        // 初始化父节点数组
        count = n;
        for (int i = 0; i < n; ++i) parent.push_back(i);
    }
    void union_(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp != rootq) {
            parent[rootq] = parent[rootp];
            count--;
        }
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool connectd(int p, int q) {
        return find(p) == find(q);
    }
    int count_() {
        return count;
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        UF uf(n);
        for (auto edge : edges) {
            uf.union_(edge[0], edge[1]);
        }
        return uf.count_();
    }
};

🥂 990. 等式方程的可满足性 [等式] (并查集)

class UF {
private:
    vector<int> parent;     // 某个节点的父节点
public:
    UF(int n) {
        for (int i = 0; i < n; ++i) parent.push_back(i);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_(int p, int q) {
        int rootp = find(p), rootq = find(q);
        if (rootp != rootq) {
            parent[rootp] = rootq;
        }
    }
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UF uf(26);
        for (auto e : equations) {
            if (e[1] == '=') {
                uf.union_(e[0] - 'a', e[3] - 'a');
            }
        }
        // 判断不相等的数在一个连通集不
        for (auto e : equations) {
            if (e[1] == '!') {
                if (uf.connected(e[0] - 'a', e[3] - 'a')) {
                    return false;
                }
            }
        }
        return true;
    }
};

🥂 1135. 最低成本连通所有城市 [图] [权重和] (并查集) (贪心)

class UF {
private:
    int count = 0;          // 连通分量
    vector<int> parent;     // 父节点数组
public:
    UF (int n) {
        count = n;
        for (int i = 0; i < n; ++i) parent.push_back(i);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union_(int p, int q) {
        int rootp = find(p), rootq = find(q);
        if (rootp != rootq) {
            parent[rootp] = rootq;
        }
        count--;
    }
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
    int count_() {
        return count;
    }
};

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        UF uf(n + 1);
        int res = 0;
        sort(connections.begin(), connections.end(), [](vector<int>& a, vector<int>& b) {
            return a[2] < b[2];
        });
        for (auto edge : connections) {
            int p = edge[0], q = edge[1], weight = edge[2];
            if (uf.connected(p, q)) {
                continue;
            }
            res += weight;
            uf.union_(p, q);
        }
        return uf.count_() == 2 ? res : -1;
    }
};