07.02 第 073 ~ 074 题（ 第 05 ~ 08 天）

07.02 第 073 ~ 074 题（ 第 05 ~ 08 天）

路径总和

分析

深度优先遍历：

  • 如果当前节点为空，返回false。
  • 否则更新targetSum -= root->val；
  • 当前节点是叶子节点，如果targetSum == 0，返回true，否则返回false。
  • 递归左子树或右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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 hasPathSum(TreeNode* root, int targetSum) {
        // 处理边界
        if(root == nullptr){
            return false;
        }
        targetSum -= root->val;
        // 如果是叶子节点
        if(root-> left == nullptr && root->right == nullptr){
            if(targetSum == 0){
                return true;
            }
            else{
                return false;
            }
        }
        // 否则递归左右子树
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

路径总和II

分析

与上一题类似，需要一个数组去存储路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(root, targetSum, 0, res, path);
        return res;
    }
    void dfs(TreeNode* root, int targetSum, int curSum, vector<vector<int>>& res, vector<int> path){
        if(root == nullptr){
            return;
        }
        curSum += root->val;
        path.push_back(root->val);
        // 如果是叶子节点
        if(root->left == nullptr && root->right == nullptr){
            if(curSum == targetSum){
                res.push_back(path);
                return;
            }
        }
        dfs(root->left, targetSum, curSum, res, path);
        dfs(root->right, targetSum, curSum, res, path);
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

[!NOTE]
想一想path带不带&的区别。

对称二叉树

递归

检查左右子树是否相等:

  • 左右子树有一个为空，不相等；都为空，相等。
  • 检查左右子树值以及左子树的右子树和右子树的左子树是否相等，以及左子树的左子树和右子树的右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 isSymmetric(TreeNode* root) {
        return isEqual(root->left, root->right);
    }
    bool isEqual(TreeNode* leftT, TreeNode* rightT){
        if(leftT == nullptr || rightT == nullptr){
            return leftT == rightT;
        }
        return leftT->val == rightT->val && isEqual(leftT->left, rightT->right) && isEqual(leftT->right, rightT->left);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

迭代

首先引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 isSymmetric(TreeNode* root) {
        return check(root, root);
    }
    bool check(TreeNode* leftT, TreeNode* rightT){
        queue<TreeNode*> que;
        que.push(leftT);
        que.push(rightT);
        while(!que.empty()){
            TreeNode* leftNode = que.front();
            que.pop();
            TreeNode* rightNode = que.front();
            que.pop();
            // 为空
            if(leftNode == nullptr && rightNode == nullptr) continue;
            // 其中有一个为空或者值不相等，返回false
            if((leftNode == nullptr || rightNode == nullptr) || leftNode->val != rightNode->val){
                return false;
            }
            que.push(leftNode->left);
            que.push(rightNode->right);
            que.push(leftNode->right);
            que.push(rightNode->left);
        }
        return true;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

[!NOTE]
有空看一下递归算法讲解1和递归算法讲解2

二叉树中的最大路径和

分析

用一个dfs函数求到当前节点的链的和，也就是中间不能拐弯，即当前节点值加左右子树的较大值。最后求直径和，即左子树链值加右子树链值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    // 返回链和，途中更新ans
    int dfs(TreeNode* root){
        // 处理边界
        if(root == nullptr){
            return 0;
        }
        int leftLen = max(dfs(root->left), 0);
        int rightLen = max(dfs(root->right), 0);
        // 更新答案
        ans = max(ans, leftLen + rightLen + root->val);
        // 返回链和
        return max(leftLen, rightLen) + root->val;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

二叉树的右视图

深度优先遍历

如果当前节点为空，结束遍历，否则，先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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:
    vector<int> ans;
    vector<int> rightSideView(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* root, int depth){
        if(root == nullptr){
            return;
        }
        if(depth == ans.size()){
             ans.push_back(root->val);
        }
        dfs(root->right, depth + 1);
        dfs(root->left, depth + 1);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

广度优先遍历

层序遍历，取每一层最右边的节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(root == nullptr){
            return ans;
        }

        queue<TreeNode*> que;
        que.push(root);

        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                // 如果是这一层的最后一个节点
                if(i == size - 1){
                    ans.push_back(node->val);
                }
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);             
            }
        }
        return ans;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

翻转二叉树

分析

如果节点为空，就不用翻转；否则递归翻转左右子树，然后再反转左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return root;
        }
        TreeNode* leftT = invertTree(root->left);
        TreeNode* rightT = invertTree(root->right);
        root->left = rightT;
        root->right = leftT;
        return root;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

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

分析

递归思路：当前序遍历数组为空时，返回空。否则在中序遍历数组中找到当前根的位置，并将其分成左右两棵子树，根据左右子树的节点数将前序、中序数组都分成左右子树两部分，然后递归得到左右子树的根，再让当前根连接左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 递归结束
        if(preorder.size() == 0){
            return nullptr;
        }
        // 根节点
        TreeNode* root = new TreeNode(preorder[0]);
        // 在中序遍历中找到它
        int i = 0;
        for(; i < inorder.size(); i++){
            if(inorder[i] == root->val){
                break;
            }
        }
        // 计算左右子树节点数
        int leftSize = i - 0;
        // 计算左右子树的前序、中序遍历数组
        vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + leftSize);
        vector<int> rightPre(preorder.begin() + 1 + leftSize, preorder.end());
        vector<int> leftIn(inorder.begin(), inorder.begin() + leftSize);
        vector<int> rightIn(inorder.begin() + 1 + leftSize, inorder.end());
        // 递归遍历得到左右子树的根
        TreeNode* left = buildTree(leftPre, leftIn);
        TreeNode* right = buildTree(rightPre, rightIn);
        root->left = left;
        root->right = right;
        return root;
    }
};
  • 时间复杂度：$O(n^2)$，最坏情况下二叉树是一条链，我们需要递归 O(n) 次，每次都需要 O(n) 的时间查找 preorder[0] 和复制数组。
  • 空间复杂度：$O(n^2)$。

优化

  • 用一个哈希表（或者数组）预处理 inorder 每个元素的下标，这样就可以 O(1) 查到 preorder[0] 在 inorder 的位置，从而 O(1) 知道左子树的大小。
  • 把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 哈希表预存储
        int n = preorder.size();
        unordered_map<int, int> index;
        for(int i = 0; i < n; i++){
            index[inorder[i]] = i;
        }

        function<TreeNode*(int, int, int, int)> dfs = [&](int preLeft, int preRight, int inLeft, int inRight) -> TreeNode*{
            // 递归结束
            if(preLeft == preRight){
                return nullptr;
            }
            // O(1)时间在中序遍历中找到根节点
            int leftSize = index[preorder[preLeft]] - inLeft;
            // 递归遍历左右子树
            TreeNode* left = dfs(preLeft + 1, preLeft + 1 + leftSize, inLeft, inLeft + leftSize);
            TreeNode* right = dfs(preLeft + 1 + leftSize, preRight, inLeft + leftSize + 1, inRight);
            return new TreeNode(preorder[preLeft], left, right);
        };

        return dfs(0, n, 0, n);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

验证二叉搜索树

虽然题目是 int 类型，但开始递归的时候，left 需要比所有节点值都要小，right 需要比所有节点值都要大，如果节点值刚好是 int 的最小值/最大值，就没有这样的 left 和 right 了，所以需要用 long 类型。

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 isValidBST(TreeNode* root) {
        return hepler(root, LLONG_MIN, LLONG_MAX);
    }
    bool hepler(TreeNode* root, long long left, long long right){
        if(root == nullptr){
            return true;
        }
        long long x = root->val;
        if(x <= left || x >= right){
            return false;
        }
        return hepler(root->left, left, x) && hepler(root->right, x, right);
    }
};

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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:
    long long pre = LLONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        if(!isValidBST(root->left) || root->val <= pre){
            return false;
        }
        pre = root->val;
        return isValidBST(root->right);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

平衡二叉树

分析

计算左子树深度，计算右子树深度，如果相差大于1则返回-1，否则返回左右子树高度。最后判断root的高度是否为-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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 isBalanced(TreeNode* root) {
        return checkBalance(root) != -1;
    }

    int checkBalance(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int left = checkBalance(root->left);
        if (left == -1) {
            return -1;  // 左子树不平衡，直接返回
        }

        int right = checkBalance(root->right);
        if (right == -1) {
            return -1;  // 右子树不平衡，直接返回
        }

        if (abs(left - right) > 1) {
            return -1;  // 当前节点不平衡
        }

        return max(left, right) + 1;  // 返回当前节点的高度
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

岛屿数量

深度优先搜索

DFS 有两个要素：「访问相邻结点」和「判断 base case」。网格结构的相邻结点就是上下左右四个，边界是超出网格范围的格子。

网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点。这是因为，网格结构本质上是一个「图」，在图中遍历时，自然可能遇到重复遍历结点。避免这样的重复遍历，需要标记已经遍历过的格子。以岛屿问题为例，我们需要在所有值为 1 的陆地格子上做 DFS 遍历。每走过一个陆地格子，就把格子的值改为 2，这样当我们遇到 2 的时候，就知道这是遍历过的格子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }

        return ans;
    }
    void dfs(vector<vector<char>>& grid, int row, int col){
        // 边界处理
        if(!isArea(grid, row, col)){
            return;
        }

        // 避免重复遍历
        if(grid[row][col] != '1'){
            return;
        }
        grid[row][col] = '2';   // 标记已遍历过

        // 访问上下左右四个节点
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }
    // 判断是否越界
    bool isArea(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >=0 && col < n){
            return true;
        }
        return false;
    }
};
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)，最坏情况下，整个棋盘是一个岛屿，递归的深度会达到mn。

广度优先搜索

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被标记为 2。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // 广度优先搜索
                if(grid[i][j] == '1'){
                    ans++;
                    queue<pair<int, int>> que;  // 队列存储坐标
                    que.push({i, j});
                    grid[i][j] = '2';   // 标记已访问
                    // 广度优先
                    while(!que.empty()){
                        auto rc = que.front();
                        que.pop();
                        int row = rc.first, col = rc.second;
                        // 将上下左右四个放入队列
                        if(isArea(grid, row - 1, col)){
                            que.push({row - 1, col});
                            grid[row-1][col] = '2';
                        }
                        if(isArea(grid, row + 1, col)){
                            que.push({row + 1, col});
                            grid[row+1][col] = '2';
                        }
                        if(isArea(grid, row, col - 1)){
                            que.push({row, col - 1});
                            grid[row][col-1] = '2';
                        }
                        if(isArea(grid, row, col + 1)){
                            que.push({row, col + 1});
                            grid[row][col + 1] = '2';
                        }                                                
                    }
                }
            }
        }

        return ans;
    }

    // 判断是否越界
    bool isArea(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >=0 && col < n && grid[row][col] == '1'){
            return true;
        }
        return false;
    }
};

isArea逻辑优化：在其中添加对grid[row][col] == '1'的判断，这样在上下左右四个节点的时候无需再判断，减少不必要的递归。

  • 时间复杂度：O(mn)
  • 空间复杂度：O(min(m,n))，这里可以理解为，广度优先每次向外扩展一圈，直到超出网格边界或不为1，那么最坏情况下，超过较短边界的时候程序就会结束。

并查集

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。

在 C++ 中，为成员函数加上 const 表示该函数不会修改类的成员变量，从而保证这个函数是“只读”的，适合用于访问类的状态而不改变它。具体到你的代码，getCount() 是用来获取岛屿数量的，只需读取 count 值，不涉及任何修改操作，所以可以在其声明后加上 const。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;

public:
    UnionFind(vector<vector<char>>& grid) {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        
        // 初始化并查集
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    parent.push_back(i * n + j);
                    count++;
                }else{
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }

    int find(int i){
        if(parent[i] != i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void unite(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        // 按秩合并
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if(rank[rootx] == rank[rooty]){
                rank[rootx] += 1;
            }
            count--;
        }
    }

    int getCount() const {
        return count;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        UnionFind uf(grid); // 初始化并查集

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    grid[i][j] = '2';   // 标记已访问过
                    // 合并上下左右节点
                    if(isArea(grid, i - 1, j)){
                        uf.unite(i * n + j, (i-1) * n + j);
                    }
                    if(isArea(grid, i + 1, j)){
                        uf.unite(i * n + j, (i+1) * n + j);
                    }
                    if(isArea(grid, i, j - 1)){
                        uf.unite(i * n + j, i * n + (j-1));
                    }
                    if(isArea(grid, i, j + 1)){
                        uf.unite(i * n + j, i * n + (j+1));
                    }                                                            
                }
            }
        }

        return uf.getCount();
    }

    // 判断是否越界
    bool isArea(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >=0 && col < n && grid[row][col] == '1'){
            return true;
        }
        return false;
    }
};
  • 时间复杂度：O(MN×α(MN))，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，单次操作的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，函数 α(x) 的值不会超过 5，因此也可以看成是常数时间复杂度。
  • 空间复杂度：O(MN)，这是并查集需要使用的空间。

岛屿的最大面积

分析

与上面的思想类似，但需要在每次进入一个岛屿时维护当前岛屿面积的变量，并不断更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    int area = 0;
                    dfs(grid, i, j, area);
                    ans = max(ans, area);
                }
            }
        }

        return ans;
    }
    void dfs(vector<vector<int>>& grid, int row, int col, int& area){
        // 边界处理
        if(!isArea(grid, row, col)){
            return;
        }
        // 避免重复遍历
        if(grid[row][col] != 1){
            return;
        }
        // 标记已访问
        grid[row][col] = 2;
        area++;
        // 访问上下左右
        dfs(grid, row - 1, col, area);
        dfs(grid, row + 1, col, area);
        dfs(grid, row, col - 1, area);
        dfs(grid, row, col + 1, area);
    }
    bool isArea(vector<vector<int>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >=0 && row < m && col >= 0 && col < n){
            return true;
        }
        return false;
    }
};
  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)

求根节点到叶节点的数字之和

分析

递归思路：当前节点为叶子节点，将当前路径和加入答案，结束递归。否则递归计算左右子树的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    int ans = 0;
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    void dfs(TreeNode* node, int x){
        if(node == nullptr){
            return;
        }
        
        x = x * 10 + node->val;
        // 是叶子结点
        if(node->left == node->right){
            ans += x;
            return;
        }
        dfs(node->left, x);
        dfs(node->right, x);
    }
};

也可以用有返回值的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    int sumNumbers(TreeNode *root, int x = 0) {
        if (root == nullptr) {
            return 0;
        }
        x = x * 10 + root->val;
        if (root->left == root->right) { // root 是叶子节点
            return x;
        }
        return sumNumbers(root->left, x) + sumNumbers(root->right, x);
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

总结

这一部分的题目主要是对二叉树的深度优先遍历，练习了一些递归的写法，在岛屿题目中学到了网格的遍历方法，又复习了一下并查集。之后还需要再复习，多练习一些相关的题目。

算法笔记 > 面试篇
#leetcode-notes
07.02 第 073 ~ 074 题（ 第 05 ~ 08 天）
http://example.com/2024/11/06/posts/0702/
作者
Xuan Yang
发布于
2024年11月6日
许可协议