LeetCode.200.547.117.572(广度优先搜索&深度优先搜索)

200.岛屿数量

class Solution {
  public:
    int numIslands(vector<vector<char>> &grid) {
        int sum = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count(grid, j, i);
                    sum++;
                }
            }
        }
        return sum;
    }
    void count(vector<vector<char>> &grid, int x, int y) {
        if (grid[y][x] != '1')
            return;
        else
            grid[y][x] = '0';
        int directionX[4] = {-1, 0, 1, 0};
        int directionY[4] = {0, -1, 0, 1};
        for (int i = 0; i < 4; i++) {
            int nextX = x + directionX[i];
            int nextY = y + directionY[i];
            if (nextX < 0 || nextX > grid[0].size() - 1 || nextY < 0 || nextY > grid.size() - 1) {
                continue;
            }
            count(grid, nextX, nextY);
        }
    }
    // 49/49 cases passed (28 ms)
    // Your runtime beats 89.69 % of cpp submissions
    // Your memory usage beats 78.39 % of cpp submissions (11.9 MB)
};

547.省份数量

class Solution {
  public:
    int findCircleNum(vector<vector<int>> &isConnected) {
        int count = 0;
        for (int i = 0; i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected[0].size(); j++) {
                if (isConnected[i][j]) {
                    find(isConnected, j, i);
                    count++;
                }
            }
        }
        return count;
    }
    void find(vector<vector<int>> &isConnected, int x, int y) {
        if (isConnected[y][x] == 0) {
            return;
        } else {
            isConnected[y][x] = 0;
            isConnected[x][y] = 0;
            for (int i = 0; i < isConnected[0].size(); i++) {
                if (isConnected[x][i])
                    find(isConnected, i, x);
            }
        }
    }
    // 113/113 cases passed (24 ms)
    // Your runtime beats 38.43 % of cpp submissions
    // Your memory usage beats 22.72 % of cpp submissions (13.6 MB)
    //*用并查集更好
};

117.填充每个节点的下一个右侧节点指针-ii

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
  public:
    Node *connect(Node *root) {
        Node *temp = root;
        while (temp) {
            if (temp->left) {
                link(temp);
                temp = temp->left;
            } else if (temp->right) {
                link(temp);
                temp = temp->right;
            } else
                temp = temp->next;
        }
        return root;
    }
    void link(Node *root) {
        if (!root)
            return;
        if (!root->left && !root->right) {
            link(root->next);
            return;
        }
        Node *opt;
        if (!root->right) {
            opt = root->left;
        } else if (!root->left) {
            opt = root->right;
        } else {
            opt = root->right;
            root->left->next = root->right;
        }
        Node *temp = root->next;
        while (temp) {
            if (temp->left || temp->right)
                break;
            else
                temp = temp->next;
        }
        if (!temp)
            opt->next = nullptr;
        else if (!temp->left)
            opt->next = temp->right;
        else
            opt->next = temp->left;
        link(temp);
    }
    // 55/55 cases passed (8 ms)
    // Your runtime beats 96.36 % of cpp submissions
    // Your memory usage beats 99.96 % of cpp submissions (16.7 MB)
};

572.另一棵树的子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
  public:
    bool isSubtree(TreeNode *root, TreeNode *subRoot) {
        if (!root)
            return 0;
        return search(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
    bool search(TreeNode *root, TreeNode *subRoot) {
        if (!subRoot && !root)
            return 1;
        if (!subRoot || !root || root->val != subRoot->val) {
            return 0;
        } else {
            if (!root->left && !root->right) {
                return !subRoot->left && !subRoot->right;
            }
            return (search(root->left, subRoot->left) && search(root->right, subRoot->right));
        }
    }
    // 182/182 cases passed (16 ms)
    // Your runtime beats 89.95 % of cpp submissions
    // Your memory usage beats 92.19 % of cpp submissions (27.9 MB)
};