🚀 更新判断环形链表

前言

​ 初次刷题的感想：思路很简单，实现起来却很困难。为了丰富编码经验本篇文章来记录刷题的大体思路，我会提供一些C语言代码提供参考。希望对你们也有帮助。

​ 在实践中去体验算法的思想，才能对算法有深刻的理解。话不多说让我们开启这趟体验算法乐趣的列车吧。

69. x 的平方根

题目描述

​ 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

暴力解法

代码实现

1
2
3
4
5
6
7
8
9
10
int mySqrt(int x) {
    long int i;
    for (i = 1; i <=x; i++) {
        if (i * i > x)
            return i - 1;
        else if (i * i == x)
            return i;
    }
        return 0;
}

算法分析

  1. int mySqrt(int x) {：定义一个名为mySqrt的函数，它接受一个整数x作为参数，并返回一个整数。
  2. long int i;：声明一个长整型变量i，用于迭代和存储当前的整数。
  3. for (i = 1; i <= x; i++) {：初始化i为1，然后进入一个循环，该循环将继续执行，直到i大于x。
  4. if (i * i > x)：在循环中，首先检查i的平方是否大于x。
  5. return i - 1;：如果i的平方大于x，则i - 1是小于或等于x的最大的平方根。函数返回i - 1。
  6. else if (i * i == x)：如果i的平方等于x，那么i就是x的平方根。
  7. return i;：在这种情况下，函数直接返回i。
  8. }：这是for循环的结束。
  9. return 0;：处理特殊情况，在本函数中并没有提供出错处理机制，主要是为了突出代码逻辑。

总结

​ 这个函数的时间复杂度是O(sqrt(x))，因为它需要迭代检查直到i的平方大于x。尽管这个方法简单易懂，但对于较大的x值，它的效率较低。

二分查找法

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int mySqrt(int x) {
    long int low = 1;
    long int high = x;
    while (low <= high) {
        long int mid = low+(high-low)/2;
        if (mid * mid > x) {
            high = mid - 1;
        } else if (mid * mid < x) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return low-1;
}

算法分析

​ 这段代码的思想是利用二分查找算法来逼近一个非负整数的平方根。二分查找是一种在有序数组中查找特定元素的搜索算法。在这个场景下，它被用来在一个范围内搜索整数的平方根。

​ 二分查找的基本思想是不断地将搜索范围缩小一半，直到找到目标值或确定目标值不存在于范围内。在这段代码中，搜索的范围初始化为从1到x（输入的非负整数），而目标是找到一个数，其平方尽可能接近但不超过x。

每次迭代中，代码计算中间值mid，然后检查mid的平方与x的关系：

  • 如果mid * mid大于x，说明mid的平方太大了，因此将搜索范围的上界（high）调整为mid - 1。
  • 如果mid * mid小于x，说明mid的平方太小了，因此将搜索范围的下界（low）调整为mid + 1。
  • 如果mid * mid等于x，说明找到了精确的平方根，直接返回mid。

​ 这个过程会一直重复，直到搜索范围的下界大于上界（即low > high），此时循环结束。由于每次迭代都将搜索范围减半，这个算法的效率是对数级别的，相比于线性搜索或其他更复杂的算法来说是非常高效的。

​ 最后，如果循环结束时没有找到精确的平方根（即没有找到mid * mid == x的情况），函数会返回搜索范围下界的前一个值（low - 1）。这是因为在最后一次迭代中，low和high会相等，而low的平方根是小于或等于x的最大的整数。

总结

​ 总体来说，这段代码实现了一个高效的算法来逼近一个非负整数的平方根，并且返回了尽可能接近但不超过x的整数平方根。

  • 时间复杂度：O(log⁡x)O(\log x)，即为二分查找需要的次数。
  • 空间复杂度：O(1)O(1)。

牛顿法

牛顿迭代公式

​ 首先，选择一个接近函数f(x)f(x)零点的x0x_0，计算相应的f(x0)f(x_0)和切线斜率f′(x0)f'(x_0)。然后我们计算穿过点(x0,f(x0))(x_0,f(x_0))，并且斜率为f′(x0)f'(x_0)的直线和xx轴的交点xx坐标，也就是求如下方程的解：

0=(x−x0)⋅f′(x0)+f(x0)0=(x-x_0) \cdot f'(x_0)+f(x_0)

​ 我们将新求得的点的xx坐标命名x1x_1，通常x1x_1会比x0x_0更接近方程f(x)=0f(x) = 0的解。因此我们可以利用x1x_1开始下一轮迭代。迭代公式如下：

xn−1=xn−f(xn)f′(xn)x_{n-1} = x_n-\frac{f(x_n)}{f'(x_n)}

已有证明牛顿迭代法的二次收敛必须满足一下条件：

​ f′(x)≠0f'(x) \neq 0；对于所有的x∈Ix \in I，其中II为区间[α−r,α+r][\alpha-r,\alpha+r]，且x0x_0在区间II内，即r≥∣a−x0∣r\ge |a-x_0| 的；对于所有x∈I,f′′(x)x\in I,f''(x)是连续的；x0x_0足够接近根α\alpha 。

​ 然而当f(x)=0f(x)=0在x=ax=a处有m重根时，这时牛顿法会降为线性收敛，虽然使用牛顿法也可以继续算下去，但收敛的速度会减慢。

代码实现

1
2
3
4
5
6
7
8
9
10
int mySqrt(int x) {
    if(x==0) return 0;
   double C = x,x0 = x;
   while(1){
       double xi = 0.5*(x0+C/x0);
       if(x0-xi<1e-5) break;
       x0 = xi;
   }
   return (int)x0;
}

算法分析

  1. 函数首先检查输入 x 是否为0。如果是，它直接返回0，因为0的平方根是0。

  2. 接下来，函数初始化两个双精度浮点数变量 C 和 x0，其中 C 被设置为 x，而 x0 也被设置为 x。C 实际上是我们要找的平方根的目标值（即 x），而 x0 是我们的初始猜测值。

  3. 然后，函数进入一个无限循环（由 while(1) 表示），在该循环中，它使用牛顿法的迭代公式来更新 x0 的值。迭代公式是 xi = 0.5 * (x0 + C / x0)，其中 xi 是新的猜测值。

  4. 在每次迭代中，函数检查 x0 和 xi 之间的差是否小于一个很小的值（1e-5，即0.00001）。如果是，这意味着 x0 已经非常接近实际的平方根了，因此函数跳出循环。

  5. 最后，函数将 x0 转换为整数并返回。这是因为函数的返回类型是 int，而牛顿法可能产生一个浮点数的结果，我们需要将其转换为整数。

总结

​ 其实理解起来不难其实就是函数求零点问题，其中利用迭代来近似零点位置。其中最影响算法效率的就是精度的选取，由于计算的是平方根精度不会出现负数毕竟曲线是凹的。你也可以去求高次开方，就是一个近似找零点的过程。

  • 时间复杂度：O(log⁡x)O(\log x)，此方法是二次收敛的，相较于二分查找更快。
  • 空间复杂度O(1)O(1)。

70. 爬楼梯

题目描述

​ 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

​ 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

动态规划

算法思想

这个题你列出几项你就会发现这个就是斐波那契数列求解问题，公式和斐波那契数列也极为相似：

f(x)=f(x−1)+f(x−2)f(x) = f(x-1)+f(x-2)

你可以考虑递归实现，当然递归很简单但要考虑你的栈是否会溢出。

我也考虑过使用排列组合，然后发现阶乘的结果数据太大而无法存储。

算法思想总之一句话：求解斐波那契数列。这里使用一种滚动数组的思想来实现迭代计算。

代码实现

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) {
    int i;
    int bp[3]={0};
    bp[2] = 1;
    for (i = 0; i < n; i++) {
        bp[0] =bp[1] ;
        bp[1] = bp[2];
        bp[2] = bp[0]+bp[1];
    }
    return bp[2];
}

算法步骤

  1. int bp[3]={0};：定义了一个大小为3的整数数组bp，并初始化为0。这里只需要3个元素是因为在任何时候，到达第i阶的方法只依赖于到达第i-1阶和第i-2阶的方法数。
  2. bp[2] = 1;：初始化bp[2]为1，表示到达第2阶有1种方法，即爬2个台阶。
  3. 接下来的for循环用于计算到达每一阶的方法数。
    • bp[0] = bp[1];：到达第i阶的方法数（即bp[0]）等于到达第i-1阶的方法数（即bp[1]）。
    • bp[1] = bp[2];：到达第i-1阶的方法数（即bp[1]）等于到达第i-2阶的方法数（即bp[2]）。
    • bp[2] = bp[0] + bp[1];：到达第i+1阶的方法数（即bp[2]）等于到达第i阶的方法数（即bp[0]）和到达第i-1阶的方法数（即bp[1]）之和。这是因为你可以从第i阶爬1个台阶到达第i+1阶，或者从第i-1阶爬2个台阶到达第i+1阶。
  4. 最后，返回bp[2]，即到达第n阶的方法数。

总结

​ 这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为它只使用了常数个变量来存储状态，并且没有进行递归调用。这使得它在处理大问题时比递归方法更加高效。

矩阵快速幂

​ 这个方法需要找到递推公式，然后转化成为矩阵关系，然后计算某个矩阵的n次幂，其中涉及到矩阵运算。目前能力有限留到以后解决。

通项公式

这里我们使用线性代数的知识来找到递推的关系:

[11 10][f(n) f(n−1)]=[f(n)+f(n−1) f(n)]=[f(n+1) f(n)]\begin{bmatrix}1&1\\\ 1&0\end{bmatrix} \begin{bmatrix}f(n)\\\ f(n-1)\end{bmatrix} = \begin{bmatrix}f(n)+f(n-1)\\\ f(n)\end{bmatrix} = \begin{bmatrix}f(n+1)\\\ f(n)\end{bmatrix}

我们会发现：

[f(n+1) f(n)]=[11 10]n[f(1) f(0)]\begin{bmatrix}f(n+1)\\\ f(n)\end{bmatrix}={\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}}^n\begin{bmatrix}f(1)\\\ f(0)\end{bmatrix}

令:

M=[11 10]M=\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}

其中MM的特征方程为x2=x+1x^2=x+1

求得:x1=1+52x_1 = \frac{1+\sqrt{5}}{2},x2=1−52x_2 = \frac{1-\sqrt{5}}{2}。则：f(n)=C1x1n+C2x2nf(n) = C_1x_1^n+C_2x_2^n 将其代入初始条件f(1)=1,f(2)=1f(1)=1,f(2)=1

，得c1=15,c2=−15c_1 = \frac 1{\sqrt5},c_2=-\frac1{\sqrt{5}}，由此我们得出数列的通项公式：

f(n)=15[(1+52)n−(1−52)n]f(n) = \frac1{\sqrt5}\left[\left({\frac{1+\sqrt{5}}{2}} \right)^n -\left(\frac{1-\sqrt5}2 \right)^n\right]

代码实现

1
2
3
4
5
int climbStairs(int n) {
    double sqrt5 = sqrt(5);
    double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
    return (int)(fibn / sqrt5);
}

算法分析

  1. double sqrt5 = sqrt(5);：计算5\sqrt5的值。
  2. double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);：这是斐波那契数列的通项公式。它计算了(φn)(φ^n)和((1−φ)n)((1 - φ)^n)的差，其中φ是黄金分割数。这个公式可以用来计算斐波那契数列的第n项。
  3. return (int)(fibn / sqrt5);：将计算结果除以5\sqrt5，然后四舍五入到最近的整数，并转换为int类型返回。

总结

​ 就是通过公式求斐波那契数列的值。因为是通过公式计算整体时间复杂度是O(1)O(1)但用到了pow和sqrt函数所以时间复杂度和这两个函数有关。

83. 删除排序链表中的重复元素

题目描述

​ 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。(不带有头节点)

算法思想

​ 通过遍历链表并比较相邻节点的值来删除重复项。如果找到重复项，它会删除下一个重复的节点，并继续检查后面的节点。最后，它返回处理后的链表的头节点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* cur = head;
    while (cur->next != NULL) {
        if (cur->val == cur->next->val) {
            struct ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
        } else
            cur = cur->next;
    }
    return head;
}

算法步骤

  1. struct ListNode* deleteDuplicates(struct ListNode* head) {
    • 定义函数 deleteDuplicates，接受一个指向 ListNode 结构体的指针 head 作为参数。
  2. if (head == NULL)
    • 检查链表是否为空。
  3. return NULL;
    • 如果链表为空，直接返回 NULL。
  4. struct ListNode* cur = head;
    • 定义一个指针 cur，并将其初始化为链表的头节点。
  5. while (cur->next != NULL) {
    • 使用 while 循环遍历链表，直到 cur 到达链表的末尾。
  6. if (cur->val == cur->next->val) {
    • 检查当前节点的值是否与其下一个节点的值相同。
  7. struct ListNode* tmp = cur->next;
    • 如果相同，定义一个临时指针 tmp 并将其指向下一个节点。
  8. cur->next = cur->next->next;
    • 删除下一个节点，即让当前节点的 next 指针指向下一个节点的下一个节点。
  9. free(tmp);
    • 释放之前存储在 tmp 中的节点的内存。
  10. } else
    • 如果当前节点的值与其下一个节点的值不同…
  11. cur = cur->next;
    • 将 cur 指针移动到下一个节点。
  12. }
    • while 循环结束。
  13. return head;
    • 返回处理后的链表的头节点。

总结

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

88. 合并两个有序数组

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

双指针

算法思想

主要思想是使用两个指针分别指向两个有序数组的开始位置，然后比较两个指针所指向的元素大小，将较小的元素放入一个新的数组中，并移动相应的指针。这个过程持续进行，直到其中一个数组的所有元素都被遍历完。然后，将另一个数组中剩余的元素直接复制到新数组中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int *tmp = (int *)malloc(sizeof(int)*(m+n));
    int     k = 0;
    int     i = 0;
    int     j = 0;
    while(i<m&&j<n){
        if(nums1[i]<nums2[j])   tmp[k++] = nums1[i++];
        else                    tmp[k++] = nums2[j++];  
    }
    while(i<m)                   tmp[k++] = nums1[i++];
    while(j<n)                   tmp[k++] = nums2[j++];
    for(i = 0;i<m+n;i++)         nums1[i] = tmp[i];
    free(tmp);
}

算法步骤

  • 初始化指针 i、j 和 k 为 0。
  • 使用 while 循环比较 nums1[i] 和 nums2[j] 的大小，并将较小的元素放入 tmp[k]，然后移动相应的指针。
  • 当 nums1 或 nums2 中的任何一个数组被完全遍历后，跳出循环。
  • 使用另外两个 while 循环处理可能剩余的 nums1 或 nums2 中的元素。
  • 使用 for 循环将 tmp 中的元素复制回 nums1。
  • 使用 free 释放 tmp 的内存。

总结

这是归并排序的核心思想，没错就是合并两个有序数组。该算法在堆中申请了内存所以空间复杂度为O(m+n)O(m+n)，算法的时间复杂度主要在于整个数组的遍历也就是O(m+n)O(m+n)。

逆向双指针

算法思想

之所以使用逆向双指针是因为数组num1已经有足够的空间存储所以数据，num1的总空间和有效元素个数均已知，所以只需要从后向前比对，然后将较大者插入num1的尾部。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {

    int i = m - 1;     // nums1的索引，从后向前
    int j = n - 1;     // nums2的索引，从后向前
    int k = m + n - 1; // 合并后数组的索引，从后向前

    // 合并两个数组
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }

    // 处理nums2中剩余的元素
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

算法步骤

  1. 初始化三个指针：i指向nums1的最后一个有效元素，j指向nums2的最后一个有效元素，k指向合并后数组的最后一个位置（即nums1的末尾位置）。
  2. 在i和j都有效的情况下，比较nums1[i]和nums2[j]的值：
    • 如果nums1[i]更大，将nums1[i]放入合并后数组的最后位置（即nums1[k]），然后i和k都向前移动一位。
    • 否则，将nums2[j]放入合并后数组的最后位置（即nums1[k]），然后j和k都向前移动一位。
  3. 当i不再有效时（即i < 0），说明nums1中的所有元素都已经被处理，此时只需将nums2中剩余的元素（从j开始到末尾）依次放入nums1中即可。这一步通过第二个while循环实现。

总结

  • 由于nums1的空间已经足够大，所以我们可以直接在nums1上进行合并操作，而不需要额外的空间。
  • 时间复杂度：O(m+n)O(m+n)，指针最多移动m+nm+n次。
  • 空间复杂度O(1)O(1)，因为num1有足够空间，并没有申请额外的内存。

二叉树遍历三连击

题目描述

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

​ 二叉树遍历都是一样的题，只需要调换几个代码的顺序即可。

​ 为了方便起见这里只介绍中序遍历。

递归

递归遍历思想

  1. 开始递归：从根节点开始。
  2. 处理左子树：首先，递归地遍历左子树。由于递归的特性，这将首先遍历左子树的最左边的节点，然后逐步向右移动，直到遍历完整个左子树。
  3. 访问根节点：在遍历完左子树后，访问当前根节点。
  4. 处理右子树：然后，递归地遍历右子树。和左子树类似，这将首先遍历右子树的最左边的节点，然后逐步向右移动，直到遍历完整个右子树。
  5. 结束递归：当遍历完右子树后，递归返回。由于递归的“回溯”特性，此时将返回到上一层的节点，并继续处理该节点的下一个兄弟节点（如果有的话）。
  6. 重复：重复上述过程，直到遍历完整个二叉树。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    if (NULL != root) {
        int left_len;
        int* left_arr = inorderTraversal(root->left, &left_len);
        int right_len;
        int* right_arr = inorderTraversal(root->right, &right_len);
        *returnSize = left_len + right_len + 1;
        int* arr = (int*)malloc(sizeof(int) * (*returnSize));
        int i;
        for (i = 0; i < left_len; i++) {
            arr[i] = left_arr[i];
        }
        arr[i] = root->val;
        for (i = 0; i < right_len; i++) {
            arr[left_len + i + 1] = right_arr[i];
        }
        free(left_arr);
        free(right_arr);
        return arr;
    } else {
        *returnSize = 0;
        return NULL;
    }
}

算法步骤

  1. 递归基础情况:
    • 如果root为NULL（即当前节点为空），则*returnSize被设置为0，并返回NULL。这表示当前子树为空，无需进行任何遍历。
  2. 递归调用:
    • 对于非空节点，函数首先递归地对其左子树和右子树进行中序遍历。这通过调用inorderTraversal(root->left, &left_len)和inorderTraversal(root->right, &right_len)实现。同时，这两个调用还返回了左子树和右子树遍历结果数组的长度。
  3. 计算总长度:
    • *returnSize被设置为左子树长度left_len、右子树长度right_len和当前节点（root）的值之和，即left_len + right_len + 1。
  4. 分配数组空间:
    • 使用malloc为结果数组分配空间，大小为*returnSize个整数。
  5. 填充数组:
    • 首先，将左子树遍历的结果复制到结果数组中。
    • 然后，将当前节点的值（root->val）放入结果数组的下一个位置。
    • 最后，将右子树遍历的结果追加到结果数组中。
  6. 释放子树数组空间:
    • 使用free释放左子树和右子树遍历结果数组的空间，以避免内存泄漏。
  7. 返回结果:
    • 返回填充好的结果数组。

总结

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

迭代法

算法思想

​ 什么是递归，不就是内存栈的调用吗，那么可以这么理解只要是能通过递归实现的都可以通过迭代实现。

​ 大致步骤如下：

  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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    struct TreeNode** stack =
        (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 501);
    int* arr = (int*)malloc(sizeof(int) * 501);
    int top = 0;
    while(top>0||root!=NULL){
        while (root != NULL) {
            stack[top++] = root;
            root = root->left;
        }
        arr[(*returnSize)++] =stack[--top]->val;
        root = stack[top]->right;
    }
    return arr;
}

总结

​ 可以看出使用迭代法并没有提升算法效率，但通过迭代法可了解递归是如何实现的，这一点才是最重要的。

Morris 中序遍历

思考

​ 想象一下如果中序遍历只有右节点，那么这视乎就是链表了，那么中序遍历不就是遍历链表了吗，那问题来了二叉树变成链表吗，答案是肯定的，我们想象一下链表的结构，数据域+指针域，那树的结构呢？不也是数据域+指针域吗。不幸的是不是所有的树都那么理想，幸运的是二叉树的叶子节点是空指针域，那我们是不是可以改变它的指向呢。当然可以，我们想象一下中序遍历：左中右。好，我们从头节点开始找到最左边的节点，在这个过程中我们做一些手脚，当根节点的左节点有右节点时，我们遍历到最右节点，这时候的右节点是叶子节点，所以它的孩子节点是空指针域，这里别忘了中序遍历的规则，好我们改变右孩子的指针域指向根节点。依次类推我们边改变指向边遍历然后将指向断开，这样就不会改变原二叉树的结构。

算法思想

  1. 如果当前遍历到的节点x无左孩子，先将x的值加入答案数组，然后访问x的右孩子，即x=x.right。
  2. 如果x有左孩子，则找到x左子树上最右的节点（即左子树中序遍历的最后一个节点，也是x在中序遍历中的前驱节点），记为predecessor。
  • 如果predecessor的右孩子为空，则将其右孩子指向x，然后访问x的左孩子，即x=x.left。
  • 如果predecessor的右孩子不为空，说明已经遍历完x的左子树，此时将其右孩子置空，将x的值加入答案数组，然后访问x的右孩子，即x=x.right。
  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;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* arr = (int*)malloc(sizeof(int) * 501);
    *returnSize = 0;
    struct TreeNode* predecessor = NULL;
    while (root != NULL) {
        if (root->left != NULL) {
            predecessor = root->left;
            while (predecessor->right != NULL && predecessor->right != root) {
                predecessor = predecessor->right;
            }
            if (predecessor->right == NULL) {
                predecessor->right = root;
                root = root->left;
            } else {
                arr[(*returnSize)++] = root->val;
                predecessor->right = NULL;
                root = root->right;
            }

        } else {
            arr[(*returnSize)++] = root->val;
            root = root->right;
        }
    }
    return arr;
}

算法步骤

  1. 初始化：
    • 分配一个大小为501的整数数组arr用于存储遍历结果。
    • 初始化returnSize为0，它将用于记录遍历结果数组的大小。
    • 初始化predecessor为NULL，它用于追踪当前节点的前驱节点。
  2. 遍历：
    • 当root不为NULL时，进行循环。
    • 如果当前节点的左子树不为空：
      • 查找左子树的最右侧节点，并将其赋值给predecessor。
      • 如果predecessor的右指针为空，则将predecessor的右指针指向当前节点，并将root更新为当前节点的左子节点，继续遍历左子树。
      • 如果predecessor的右指针指向当前节点，则说明左子树已遍历完，此时将当前节点的值存储在arr数组中，并增加returnSize的值。然后，将predecessor的右指针置为NULL，并将root更新为当前节点的右子节点，继续遍历。
    • 如果当前节点的左子树为空：
      • 直接将当前节点的值存储在arr数组中，并增加returnSize的值。
      • 将root更新为当前节点的右子节点，继续遍历。
  3. 返回结果：
    • 遍历完成后，返回存储遍历结果的数组arr。

总结

​ 这种方法的好处是，它不需要额外的空间来存储指针或节点信息，只使用了一个固定大小的数组来存储遍历结果。然而，它的缺点是它会修改树的结构，但幸运的是，这些修改在遍历完成后都被恢复了。

  • 显然这里没有开辟新的空间所以空间复杂度为O(1)O(1)

  • 时间复杂度仍然是O(n)O(n)

100. 相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

深度优先遍历

算法思想

​ 深度优先遍历（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。在树形结构中，如二叉树，深度优先遍历的思想是从根节点开始，尽可能深地搜索树的分支，直到达到树的末端（即没有子节点的叶子节点），然后回溯到前一个节点，继续搜索其他未访问的分支。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p != NULL && q != NULL) {
        return isSameTree(p->left, q->left)   && 
               isSameTree(p->right, q->right) &&
               (p->val == q->val);
    } else if (p == NULL && q == NULL) {
        return true;
    } else {
        return false;
    }
}

算法步骤

  1. 基本情况（Base Cases）：
    • 如果两个节点 p 和 q 都是 NULL（即都在树的底部），则它们被认为是相同的，返回 true。
    • 如果只有一个节点是 NULL（即一个树比另一个树短），则它们不相同，返回 false。
  2. 递归情况（Recursive Cases）：
    • 如果两个节点都不是 NULL，则递归地比较它们的左子树和右子树，并同时检查它们的值是否相等。只有当左子树和右子树都相同，并且节点值也相同时，才返回 true。否则，返回 false。

总结

假设两个二叉树的节点个数分别为m和n。

  • 时间复杂度O(min⁡(m,n))O(\min(m,n))
  • 空间复杂度O(min⁡(m,n))O(\min(m,n))

广度优先遍历

算法思想

​ 广度优先遍历（BFS）也称为层序遍历。这种遍历方法是从图或树的一个未遍历的节点出发，先遍历这个节点的相邻节点，然后依次遍历每个相邻节点的相邻节点。对于树来说，广度优先遍历会首先遍历根节点，然后遍历根节点的所有子节点，接着遍历子节点的子节点，以此类推，直到遍历完所有节点。这个过程就像是从上到下对每一层进行依次访问，每一层中从左到右（或从右到左）访问节点，访问完一层就进入下一层，直到没有节点可以访问为止。广度优先遍历通常使用队列来实现。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL && q == NULL) {
        return true;
    } else if (p == NULL || q == NULL) {
        return false;
    }
    struct TreeNode** que1 =
        (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1024);
    struct TreeNode** que2 =
        (struct TreeNode**)malloc(sizeof(struct TreeNode*)*1024);
    int front1 = 0, rear1 = 0;
    int front2 = 0, rear2 = 0;
    que1[rear1++] = p;
    que2[rear2++] = q;
    while (front1 < rear1 && front2 < rear2) {
        struct TreeNode* node1 = que1[front1++];
        struct TreeNode* node2 = que2[front2++];
        if (node1->val != node2->val) {
            return false;
        }
        struct TreeNode* left1 = node1->left;
        struct TreeNode* right1 = node1->right;
        struct TreeNode* left2 = node2->left;
        struct TreeNode* right2 = node2->right;
        if ((left1 == NULL) ^ (left2 == NULL)) {
            return false;
        }
        if ((right1 == NULL) ^ (right2 == NULL)) {
            return false;
        }
        if (left1 != NULL) {
            que1[rear1++] = left1;
        }
        if (right1 != NULL) {
            que1[rear1++] = right1;
        }
        if (left2 != NULL) {
            que2[rear2++] = left2;
        }
        if (right2 != NULL) {
            que2[rear2++] = right2;
        }
    }
    return true;
}

算法分析

  1. 函数首先检查了两个树的根节点p和q是否都为空，如果是，则返回true，表示两棵空树是相同的。
  2. 接着检查其中一个树为空而另一个不为空的情况，如果是这样，则返回false，因为空树和非空树显然不同。
  3. 然后初始化两个队列que1和que2，并且只分配了一个树节点指针的空间。
  4. 定义了四个变量front1、rear1、front2、rear2来作为两个队列的左右指针，用于追踪队列中的元素。
  5. 将两棵树的根节点分别入队到que1和que2中，并开始循环直到两个队列都为空。
  6. 在循环中，首先取出两个队列的头部节点进行比较，如果值不相等，则立即返回false。
  7. 接着检查这两个节点的左右子节点是否存在，如果只有一个存在而另一个不存在，则返回false。
  8. 如果左子节点存在，则将其加入到相应的队列中。
  9. 同样的操作也应用于右子节点。
  10. 最后检查两个队列是否同时为空，如果是则返回true，否则返回false。并且由于每次循环都会同时处理一个队列中的一个节点，所以最终当循环结束时如果两棵树相同，那么两个队列必然同时为空。

总结

​ 广度优先遍历其中最大的问题就是确定队列的大小，在这里我直接将队列写死了目的是为了突出逻辑，如果动态更改队列大小会有过多代码逻辑，而在这里我主要是为了突出广度优先遍历的思想。总之但凡是广度优先遍历绝对少不了队列。

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(n)O(n)

101. 对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

广度优先(迭代法)

算法思想

​ 创建两个队列分布存储左子树和右子树，然后迭代出队判断两个节点值是否相同，然后再对比其相对孩子节点，如果孩子节点满足条件就将孩子节点入队。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSymmetric(struct TreeNode* root) {
    if(root->right==NULL&&root->left==NULL){
        return true;
    }else if(root->right==NULL||root->left==NULL){
        return false;
    }
    struct TreeNode **left_que = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*501);
    struct TreeNode **right_que = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*501);
    int front = 0; int rear = 0;
    left_que[rear] = root->left;
    right_que[rear++] = root->right;
    while(front<rear){
        struct TreeNode* node1 = left_que[front];
        struct TreeNode* node2 = right_que[front++];
        if(node1->val!=node2->val) return false;
        struct TreeNode* left1 = node1->left;
        struct TreeNode* right1 = node1->right;
        struct TreeNode* left2 = node2->left;
        struct TreeNode* right2 = node2->right;
        if((left1==NULL)^(right2==NULL)) return false;
        if((right1==NULL)^(left2==NULL)) return false;
        if(left1!=NULL&&right2!=NULL){
            if(left1->val==right2->val){
                left_que[rear] = left1;
                right_que[rear++] = right2;
            }else{
                return false;
            }
        }
        if(right1!=NULL&&left2!=NULL){
            if(right1->val==left2->val){
                left_que[rear] = right1;
                right_que[rear++] = left2;
            }else{
                return false;
            }
        }
    }
    return true;
}

算法步骤

  1. 基本情况判断：

    • 如果根节点的左右子节点都为空，则它是对称的。
    • 如果根节点的左子节点或右子节点中有一个为空，则它不是对称的。

  2. 使用队列进行层次遍历：

    • 初始化两个队列 left_que 和 right_que，用于存储左右子树的节点。
    • 初始时，将根节点的左子节点和右子节点分别入队。

  3. 遍历队列：

    • 当队列不为空时，进行以下操作：

      • 从两个队列中分别取出一个节点 node1 和 node2。

      • 如果 node1 和 node2 的值不相等，则二叉树不是对称的，返回 false。

      • 检查node1 和node2

        的左右子节点是否满足对称条件：

        • 如果 node1 的左子节点为空而 node2 的右子节点不为空，或者 node1 的左子节点不为空而 node2 的右子节点为空，则二叉树不是对称的，返回 false。

      • 如果 node1 的右子节点为空而 node2 的左子节点不为空，或者 node1 的右子节点不为空而 node2 的左子节点为空，则二叉树不是对称的，返回 false。

    • 如果上述条件都满足，并且 node1 的左子节点和 node2 的右子节点的值相等，以及 node1 的右子节点和 node2 的左子节点的值也相等，则将这两个子节点分别入队。

  4. 返回结果：

    • 如果遍历结束后都没有返回 false，则说明二叉树是对称的，返回 true。

总结

使用广度优先遍历方法，时间复杂度和空间复杂度都是O(n)O(n)

(深度优先)递归

算法思想

​ 将原二叉树复制一份，然后同步递归调用，判断右节点的左孩子和左节点的右孩子和右节点的右孩子和左节点的左孩子，然后并上左节点和有节点是否相等。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool check(struct TreeNode* p, struct TreeNode* q) {
    if (!p && !q)
        return true;
    if (!p || !q)
        return false;
    return p->val == q->val && check(p->left, q->right) &&
           check(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) { return check(root, root); }

算法步骤

check 函数

这个函数接受两个二叉树的节点 p 和 q 作为参数，并返回一个布尔值，表示这两个节点是否是对称的。

  1. 如果 p 和 q 都是 NULL，则它们是对称的，返回 true。
  2. 如果 p 或 q 其中一个是 NULL，而另一个不是，则它们不是对称的，返回 false。
  3. 否则，检查 p 和 q 的值是否相等，并且 p 的左子树与 q 的右子树是否对称，以及 p 的右子树与 q 的左子树是否对称。如果都对称，则返回 true，否则返回 false。

isSymmetric 函数

这个函数接受一个二叉树的根节点 root 作为参数，并返回一个布尔值，表示这个二叉树是否是对称的。

它通过调用 check 函数并传入 root 和 root 来实现这个功能。因为对于一个对称的二叉树，其根节点的左子树应该与右子树对称。

总结

  • 空间复杂度为O(n)O(n)
  • 时间复杂度O(n)O(n)

104. 二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

深度优先遍历

算法思想

该算法的思想是基于分治策略（Divide and Conquer）来解决问题的。分治策略是一种递归算法设计模式，它将大问题分解为两个或更多个相同或相似的小问题，然后递归地解决这些小问题，最后将小问题的解合并起来得到大问题的解。

对于计算二叉树的最大深度这个问题，分治策略的思想如下：

  1. 分解：将问题分解为两个子问题，即计算左子树的最大深度和计算右子树的最大深度。
  2. 递归解决子问题：递归地调用自身来计算左子树和右子树的最大深度。递归调用会继续进行，直到到达叶子节点（即没有子节点的节点），此时返回深度0。
  3. 合并：将左子树和右子树的最大深度进行比较，取两者中的较大值，然后加上当前节点的深度（即1），得到整棵子树的最大深度。
  4. 返回结果：返回整棵子树的最大深度作为该子问题的解。

通过这种方式，算法将大问题（计算整棵二叉树的最大深度）分解为小问题（计算每个子树的最大深度），然后递归地解决这些小问题，并最终将结果合并起来得到最终答案。这种分治策略使得算法更加高效和简洁，同时也适用于解决其他具有类似结构的问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root) {
    if (root != NULL) {
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return (left > right ? left : right) + 1;
    } else {
        return 0;
    }
}

算法步骤

首先，定义了一个函数 maxDepth，它接受一个指向 TreeNode 结构的指针作为参数。这个 TreeNode 结构通常表示二叉树的节点，其中 left 和 right 是指向左子树和右子树的指针。

函数的主要逻辑如下：

  1. 基本情况（Base Case）:
    • 如果 root 为 NULL（也就是空指针，表示到达了叶子节点或树的末端），则函数返回 0。这表示该节点（或其子树）的深度为0。
  2. 递归情况（Recursive Case）:
    • 如果 root 不为 NULL，则我们需要递归地计算左子树和右子树的深度。
    • 使用 maxDepth(root->left) 计算左子树的深度，并将其值存储在变量 left 中。
    • 使用 maxDepth(root->right) 计算右子树的深度，并将其值存储在变量 right 中。
    • 最后，返回 left 和 right 中的较大值加 1。这里的 +1 是为了加上当前节点的深度。

函数的返回值就是整棵二叉树的最大深度。

总结

该算法的时间复杂度为 O(n)O(n)，空间复杂度在最坏情况下为 O(h)O(h)

广度优先

算法思想

​ 使用队列将其中一层遍历其左右孩子节点，然后再用孩子节点更新队列，计算遍历的次数就是二叉树的深度。简单来讲就是层序遍历求其层数。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct queue_node {
    struct TreeNode* tree_node;
    struct queue_node* next;
} queue;
int maxDepth(struct TreeNode* root) {
    int deep = 0;
    if (root == NULL)
        return deep;
    queue* temp;
    queue* que1 = (queue*)malloc(sizeof(queue));
    que1->tree_node = root;
    que1->next = NULL;
    queue* que2 = (queue*)malloc(sizeof(queue));
    que2->next = NULL;
    while (que1 != NULL) {
        deep++;
        queue* queue_node1 = que1;
        queue* queue_node2 = que2;
        while (queue_node1 != NULL) {
            if (queue_node1->tree_node->left != NULL &&
                queue_node1->tree_node->right != NULL) {
                queue* left = (queue*)malloc(sizeof(queue));
                left->tree_node = queue_node1->tree_node->left;
                queue* right = (queue*)malloc(sizeof(queue));
                right->tree_node = queue_node1->tree_node->right;
                right->next = NULL;
                left->next = right;
                queue_node2->next = left;
                queue_node2 = right;

            } else if (queue_node1->tree_node->left != NULL &&
                       queue_node1->tree_node->right == NULL) {
                queue* left = (queue*)malloc(sizeof(queue));
                left->tree_node = queue_node1->tree_node->left;
                left->next = NULL;
                queue_node2->next = left;
                queue_node2 = left;

            } else if (queue_node1->tree_node->left == NULL &&
                       queue_node1->tree_node->right != NULL) {
                queue* right = (queue*)malloc(sizeof(queue));
                right->tree_node = queue_node1->tree_node->right;
                right->next = NULL;
                queue_node2->next = right;
                queue_node2 = right;
            }
            queue_node1 = queue_node1->next;
        }
        while (que1 != NULL) {
            temp = que1;
            que1 = que1->next;
            free(temp);
        }
        que1 = que2->next;
        que2->next = NULL;
    }
    return deep;
}

算法步骤

  1. 定义了一个名为 queue_node 的结构体，用于表示队列中的节点。每个节点包含一个指向 TreeNode 的指针（这是二叉树的节点）和一个指向下一个 queue_node 的指针。
  2. maxDepth 函数接受一个指向 TreeNode 的指针（树的根节点）并返回树的最大深度。
  3. 函数首先检查根节点是否为 NULL。如果是，则返回深度 0。
  4. 然后，函数创建两个队列 que1 和 que2。que1 用于存储当前层的节点，而 que2 用于存储下一层的节点。
  5. 在 while 循环中，函数遍历 que1 中的所有节点，并将它们的子节点添加到 que2 中。同时，它增加深度计数器 deep。
  6. 在内部 while 循环结束后，函数清空 que1 并将其指向 que2，以便在下一次迭代中处理下一层的节点。

总结

​ 题目中节点数给到10410^4所以使用固定大小的队列会很浪费内存，在这里使用链表来实现队列。

  • 该算法的时间复杂度为 O(n)O(n)，其中 n 是树中节点的总数。

  • 该算法的空间复杂度为 O(n)O(n)，其中 n 是树中节点的总数。这是因为我们需要使用队列来存储每一层的节点，而队列中最多可能需要存储所有节点。

​ 代码实现虽说效率不高，但能够很明确的体现出算法的思想。通过这道题你能明确发现C语言的魅力，由于是面向过程的所以也就没有现成的模板往里套，所有的数据结构都要自己封装，如果你用的是面向对象的语言那么你可以直接使用容器来实现，也不用担心内存分配问题，因为编译器会帮你解决。

108. 将有序数组转换为二叉搜索树

深度优先

算法思想

算法的思想可以概括为以下步骤：

  1. 基准情况（Base Case）：如果数组为空（即 numsSize == 0），则直接返回 NULL，表示没有节点需要构建。
  2. 分解（Divide）：将有序数组分为两半。由于数组是有序的，可以选择中间的元素作为当前子树的根节点。中间元素的索引是 numsSize / 2。
  3. 递归构建子树（Conquer）：
    • 递归地构建左子树，使用数组的前半部分（从索引 0 到 index - 1）。
    • 递归地构建右子树，使用数组的后半部分（从索引 index + 1 到 numsSize - 1）。
  4. 合并（Merge）：将构建好的左子树和右子树分别连接到当前根节点的 left 和 right 指针上。
  5. 返回结果：返回当前构建的根节点。

代码实现

1
2
3
4
5
6
7
8
9
10
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    if (numsSize==0) return NULL;
        struct TreeNode* tree =
            (struct TreeNode*)malloc(sizeof(struct TreeNode));
        int index = numsSize / 2;
        tree->val = nums[index];
        tree->left = sortedArrayToBST(nums, index);
        tree->right = sortedArrayToBST(nums + index + 1, numsSize - index - 1);
        return tree;
}

算法步骤

  1. if (numsSize==0) return NULL;
    • 如果数组为空（即 numsSize 为0），则函数返回 NULL。
  2. struct TreeNode* tree = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    • 使用 malloc 分配内存来创建一个新的 TreeNode 结构体实例，并将其地址赋给指针 tree。
  3. int index = numsSize / 2;
    • 计算数组的中间索引。由于数组是有序的，中间元素将成为新BST的根节点。
  4. tree->val = nums[index];
    • 将中间元素的值赋给新节点的 val 字段。
  5. tree->left = sortedArrayToBST(nums, index);
    • 递归调用 sortedArrayToBST 函数，将数组的前半部分（从索引0到 index-1）作为参数。返回的子树将成为当前节点的左子树。
  6. tree->right = sortedArrayToBST(nums + index + 1, numsSize - index - 1);
    • 递归调用 sortedArrayToBST 函数，将数组的后半部分（从索引 index+1 到 numsSize-1）作为参数。返回的子树将成为当前节点的右子树。
  7. return tree;
    • 返回新创建的BST的根节点。

总结

只要是涉及到递归几乎都是分治法，这个方法是没有再去封装辅助函数，你也可以将它视为深度优先，其中左子树判断比较方便，右子树需要对原数组偏移，进而方便判断递归结束条件。

该算法的时间复杂度为O(n)O(n)，由于题目中给出数组是有序的所有空间复杂的为O(log⁡n)O(\log n)

迭代法

110. 平衡二叉树

题目描述

​ 给定一个二叉树，判断它是否是高度平衡的二叉树。

自顶向下递归

算法思想

​ 该算法的思想是递归地检查二叉树的每个节点，同时计算每个节点子树的高度。通过比较左子树和右子树的高度差，可以确定该节点是否平衡。如果任何节点的左右子树高度差超过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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int abs(int a) {
    if (a < 0) {
        return -a;
    } else {
        return a;
    }
}
int maxDepth(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}
int depth(struct TreeNode* root) {
    if (root != NULL) {
        return maxDepth(depth(root->right), depth(root->left)) + 1;
    } else {
        return 0;
    }
}
bool isBalanced(struct TreeNode* root) {
    if (root != NULL) {
        return isBalanced(root->left) && isBalanced(root->right) &&
               (abs(depth(root->left) - depth(root->right)) <= 1);
    } else {
        return true;
    }
}

算法步骤

  1. int abs(int a): 这个函数返回整数a的绝对值。如果a是负数，它返回-a（即正数）；否则，它直接返回a。

  2. int maxDepth(int a, int b): 这个函数返回两个整数a和b中的最大值。

  3. int depth(struct TreeNode* root): 这个函数计算以root为根的二叉树的深度。它递归地计算左右子树的深度，并返回最大深度加1（以考虑当前节点）。

  4. bool isBalanced(struct TreeNode* root): 这是主函数，用于检查以root为根的二叉树是否平衡。它递归地检查左右子树是否平衡，并且检查两个子树的深度之差是否最多为1。

总结

​ 这种递归方法的时间复杂度在最坏情况下是O(n2)O(n^2)，其中n是树中节点的数量，因为每个节点可能会被多次访问来计算高度。然而，在实际应用中，对于许多随机生成的树或具有特定性质的树，这种算法的性能通常要好得多。空间复杂度为O(n)O(n)其中n为节点的个数。

自底向上递归

思考一下

​ 上面算法有一个明显的缺陷就是重复计算子树的深度，那么我们多加一个标记来判断是否平衡，如果不平衡那么就没有必要再去计算深度了，这样时间时间复杂度不就降到O(n)O(n)了吗。

算法思想

​ 算法思想是对上面算法的改进，其中修改计算二叉树深度的函数，在里面判断二叉树是否平衡并且将深度的返回值做为标志位，因为二叉树深度一定是大于等于0的，所以用-1来做为标志，如果返回值为-1那么表明二叉树不平衡，也就没有必要做多余的判断，如果返回值大于0就是二叉树的最大深度也就是二叉树平衡的条件。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int abs(a) {
    if (a < 0) {
        return -a;
    } else {
        return a;
    }
}
int maxDepth(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}
int depth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    int left = depth(root->left);
    int right = depth(root->right);
    if (left == -1 || right == -1 || abs(left - right) > 1) {
        return -1;
    } else {
        return maxDepth(left, right) + 1;
    }
}
bool isBalanced(struct TreeNode* root) { return depth(root) >= 0; }

算法步骤

​ 代码首先定义了一个abs函数，这个函数返回给定整数的绝对值。然后定义了一个maxDepth函数，这个函数返回两个整数中的最大值。

​ depth函数是这段代码的核心。它递归地计算给定节点的左子树和右子树的高度（深度）。如果节点为空，则高度为0。然后，它检查左子树和右子树的高度差是否大于1，或者左子树或右子树的高度是否为-1（表示该子树不是平衡的）。如果满足这些条件之一，那么depth函数返回-1，表示以当前节点为根的子树不是平衡的。否则，它返回左子树和右子树中的最大高度加1，表示以当前节点为根的子树的高度。

​ 最后，isBalanced函数检查根节点的高度是否大于等于0。如果是，那么整个树就是平衡的，函数返回true；否则，树不是平衡的，函数返回false。

总结

​ 这个算法的时间复杂度是O(n)O(n)，其中n是树中节点的数量。每个节点都会被访问一次。空间复杂度是O(h)O(h)，其中h是树的高度，这是因为在递归过程中需要用到栈空间。在最坏的情况下，当树完全不平衡时（例如，它是一棵倾斜的树），空间复杂度可能会达到O(n)O(n)。

111. 二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

深度优先

算法思想

  1. 基本情况检查：首先，检查根节点是否为空。如果为空，则树的深度为0，因为没有节点需要遍历。
  2. 左子树为空，右子树不为空的情况：如果根节点的左子树为空而右子树不为空，那么最小深度就是右子树的最小深度加1。这是因为从根节点到最近叶子节点的最短路径将只通过右子树。
  3. 右子树为空，左子树不为空的情况：如果根节点的右子树为空而左子树不为空，那么最小深度就是左子树的最小深度加1。这是因为从根节点到最近叶子节点的最短路径将只通过左子树。
  4. 左子树和右子树都不为空的情况：如果根节点的左右子树都不为空，那么最小深度将是左子树和右子树中的较小深度的那个加1。这是因为从根节点到最近叶子节点的最短路径可能通过左子树或右子树，取决于哪一边的最小深度更小。
  5. 递归调用：在上述所有情况下，算法都通过递归调用minDepth函数来计算子树的最小深度。递归是深度优先搜索的一个关键部分，因为它允许算法“深入”到树的每个分支，直到找到叶子节点为止。
  6. 累积深度：每次递归调用时，都会将子树的最小深度加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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int min(int a, int b) {
    if (a < b)
        return a;
    else
        return b;
}
int minDepth(struct TreeNode* root) {
    if (root == NULL)
        return 0;
    else if (root->right == NULL && root->left != NULL)
        return 1 + minDepth(root->left);
    else if (root->right != NULL && root->left == NULL)
        return 1 + minDepth(root->right);
    else
        return 1 + min(minDepth(root->left), minDepth(root->right));
}

算法步骤

定义了一个名为 min 的辅助函数，用于返回两个整数中的较小值。

主要的函数是 minDepth，它接受一个 TreeNode 指针（即二叉树的根节点）作为参数，并返回树的最小深度。

  • 如果根节点为 NULL（即树为空），则最小深度为 0。
  • 如果根节点有左子节点但没有右子节点，则最小深度为左子树的最小深度加 1。
  • 如果根节点有右子节点但没有左子节点，则最小深度为右子树的最小深度加 1。
  • 如果根节点既有左子节点又有右子节点，则最小深度为左子树和右子树中的较小深度的那个加 1。

这个函数通过递归地调用自身来计算每个子树的最小深度，并最终返回整个树的最小深度。

总结

​ 这种方法的时间复杂度是O(n)O(n)，其中n是树中节点的数量，因为每个节点都被访问一次。空间复杂度也是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
43
44
45
46
47
48
49
50
51
52
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct queue {
    struct TreeNode* tree_node;
    struct queue* next;
} queue;
int minDepth(struct TreeNode* root) {
    if (root == NULL)
        return 0;
    int depth = 0;
    queue* que1 = (queue*)malloc(sizeof(queue));
    que1->tree_node = root;
    que1->next = NULL;
    while (que1 != NULL) {
        queue* que2 = (queue*)malloc(sizeof(queue));
        que2->next = NULL;
        queue* head = que2;
        depth++;
        while (que1 != NULL) {
            if (que1->tree_node->left == NULL &&
                que1->tree_node->right == NULL) {
                return depth;
            }
            if (que1->tree_node->left != NULL) {
                queue* left = (queue*)malloc(sizeof(queue));
                left->tree_node = que1->tree_node->left;
                left->next = NULL;
                que2->next = left;
                que2 = left;
            }
            if (que1->tree_node->right != NULL) {
                queue* right = (queue*)malloc(sizeof(queue));
                right->tree_node = que1->tree_node->right;
                right->next = NULL;
                que2->next = right;
                que2 = right;
            }
            queue* tmp = que1;
            que1 = que1->next;
            free(tmp);
        }
        que1 = head->next;
        free(head);
    }
    return false;
}

算法步骤

​ 代码首先定义了一个结构体 queue，它包含一个指向 TreeNode 的指针和一个指向下一个 queue 结构体的指针。这个结构体被用作队列中的节点，用于广度优先搜索（BFS）遍历二叉树。

函数 minDepth 接受一个 TreeNode 指针作为参数，该指针指向二叉树的根节点。

  1. 如果根节点为 NULL，则返回深度 0。
  2. 初始化深度 depth 为 0。
  3. 创建一个队列 que1，并将根节点放入队列。
  4. 进入一个循环，直到队列为空。
    • 在每次循环中，创建一个新的队列 que2，用于存储下一层的节点。
    • 增加深度 depth。
    • 遍历当前队列 que1 中的所有节点：
      • 如果当前节点是叶子节点（没有左子节点和右子节点），则返回当前深度 depth。
      • 如果当前节点有左子节点，则创建一个新的队列节点，将左子节点放入其中，并将其添加到 que2。
      • 如果当前节点有右子节点，则创建一个新的队列节点，将右子节点放入其中，并将其添加到 que2。
      • 释放当前队列节点 que1 的内存。
    • 将 que1 更新为 que2，并释放 que2 的头节点。
  5. 如果循环结束仍未返回，则说明二叉树为空（这在逻辑上是不可能的，因为已经检查了根节点是否为 NULL），返回 false。

总结

  1. 时间复杂度

​ 时间复杂度衡量的是算法执行所需的时间随输入规模增长的趋势。在这个算法中，每个节点恰好被访问和处理一次，无论是叶子节点还是内部节点。因此，时间复杂度与二叉树中节点的总数成正比。对于包含 n 个节点的二叉树，时间复杂度是 O(n)O(n)。

  1. 空间复杂度

​ 空间复杂度衡量的是算法执行过程中所需额外空间的大小。在这个算法中，空间主要被用于存储队列中的节点。在最坏的情况下（即二叉树完全不平衡，如退化为链表），队列中可能同时包含所有节点。因此，空间复杂度也是 O(n)O(n)，其中 n 是二叉树中节点的总数。

112. 路径总和

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

深度优先

算法思想

​ 通过targetSum依次减去本层节点值，依次类推如果最后一个节点的值等于已经做完减法的targetSum的值时，那么就可以断定该路径总和等于targetSum,由于只需要找一条路径就可以，所以对孩子节点递归结果用逻辑或。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL) {
        return false;
    }
    if (root->left == NULL && root->right == NULL) {
        return targetSum == root->val;
    }
    return hasPathSum(root->left, targetSum - root->val) ||
           hasPathSum(root->right, targetSum - root->val);
}

算法步骤

接受两个参数：

  1. struct TreeNode* root：指向二叉树根节点的指针。
  2. int targetSum：目标路径和。

函数返回一个布尔值（bool），如果存在满足条件的路径，则返回true，否则返回false。

函数的工作原理如下：

  1. 首先，检查根节点是否为空。如果根节点为空，说明这棵树是空的，因此不可能存在满足条件的路径，直接返回false。
  2. 然后，检查当前节点是否为叶子节点（即没有左子节点和右子节点）。如果是叶子节点，那么只需要比较当前节点的值是否等于目标路径和targetSum，如果相等则返回true，否则返回false。
  3. 如果当前节点不是叶子节点，那么需要递归地检查其左子树和右子树中是否存在满足条件的路径。具体做法是，将目标路径和targetSum减去当前节点的值，然后分别传递给左子树和右子树的根节点，进行递归调用。
  4. 最后，使用逻辑或运算符（||）将左子树和右子树的结果进行组合。只要左子树或右子树中存在满足条件的路径，整个函数就返回true，否则返回false。

总结

​ 最坏的情况下时间复杂度和空间复杂度均为O(n)O(n)。

广度优先

算法思想

​ 首先我们设计一个队列结构体，其中val域用于求路径节点的和，我们依层遍历，使用que1来存储当前层的节点，que2来存储下一层的节点，之后我们判断当前层是否有叶子节点，如果有叶子节点判断其val域是否和targetSum相等，如果相等则存在路径，然后使用que2来更新que1依次迭代，如果不存在该路径那么会跳出循环直接返回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
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct queue {
    int val;
    struct TreeNode* tree_node;
    struct queue* next;
} queue;
bool hasPathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL)
        return false;
    queue* que1 = (queue*)malloc(sizeof(queue));
    que1->tree_node = root;
    que1->val = root->val;
    que1->next = NULL;

    while (que1 != NULL) {
        queue* que2 = (queue*)malloc(sizeof(queue));
        que2->next = NULL;
        que2->tree_node = NULL;
        queue* head = que2;
        while (que1 != NULL) {
            if (que1->tree_node->left == NULL &&
                que1->tree_node->right == NULL) {
                if (que1->val == targetSum) {
                    return true;
                }
            }
            if (que1->tree_node->left != NULL) {
                queue* left = (queue*)malloc(sizeof(queue));
                left->next = NULL;
                left->val = que1->val + que1->tree_node->left->val;
                left->tree_node = que1->tree_node->left;
                que2->next = left;
                que2 = left;
            }
            if (que1->tree_node->right != NULL) {
                queue* right = (queue*)malloc(sizeof(queue));
                right->next = NULL;
                right->tree_node = que1->tree_node->right;
                right->val = que1->val + que1->tree_node->right->val;
                que2->next = right;
                que2 = right;
            }
            queue* tmp = que1;
            que1 = que1->next;
            free(tmp);
        }
        que1 = head->next;
        free(head);
    }
    return false;
}

算法步骤

  1. typedef struct queue {...} queue; 定义了一个名为queue的结构体，包含三个成员：一个int类型的val，一个指向TreeNode的指针tree_node，以及一个指向下一个queue的指针next。
  2. hasPathSum函数接受一个指向TreeNode的指针root和一个整数targetSum作为参数。
  3. 函数首先检查根节点是否为NULL，如果是，则返回false，因为空树没有路径。
  4. 接下来，函数创建了一个名为que1的queue结构体指针，并为其分配内存。que1的tree_node成员指向root，val成员初始化为root节点的值，next成员设置为NULL。
  5. 主循环开始，当que1不为NULL时执行循环体。
  6. 在循环内部，函数创建了一个名为que2的queue结构体指针，并为其分配内存。que2的next和tree_node成员被初始化为NULL。
  7. 接下来，函数创建一个名为head的queue指针，并将其指向que2。
  8. 内部循环开始，当que1不为NULL时执行循环体。
  9. 在内部循环中，函数检查当前节点que1->tree_node是否为叶子节点（即左右子节点都为NULL）。如果是，并且que1->val等于targetSum，则函数返回true。
  10. 如果当前节点有左子节点，函数创建一个新的queue结构体指针left，为其分配内存，并设置其val、tree_node和next成员。然后，将left添加到que2之后，并更新que2指向left。
  11. 如果当前节点有右子节点，函数执行与左子节点类似的操作，创建一个名为right的新queue结构体指针，并将其添加到que2之后。
  12. 在内部循环结束后，函数释放que1指向的内存，并更新que1为head->next。然后，释放head指向的内存。
  13. 如果主循环结束后仍未找到满足条件的路径，则函数返回false。

总结

​ 这里考虑最坏的情况：时间复杂度和空间复杂度都为O(n)O(n)。

119. 杨辉三角 II

题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

递推

算法思想

​ 杨辉三角的的行其实就是组合数，这道其实是计算组合数的题，只是做了包装，当提到计算组合数的时候你一定会知道用阶乘，但你或许没有考虑过阶乘数据增长速度很离谱，一个很小的数的阶乘就很有可能导致溢出。

​ 杨辉三角的思想很简单，每一个数字等于上一行左右两个数字之和。也就是第n行的第i个数等于第n-1行的第i-1个数和第i个数的和。也就是Cni=Cn−1i+Cn−1i−1C_n^i=C_{n-1}^i+C_{n-1}^{i-1}。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getRow(int rowIndex, int* returnSize) {
    int *array1 = (int*)malloc(sizeof(int)*(rowIndex+1));
    int *array2 = (int*)malloc(sizeof(int)*(rowIndex+1));
    *returnSize = rowIndex+1;
    int i,j;
    array1[0] = 1;
    array2[0] = 1;
    for(i = 1;i<=rowIndex;i++){
        
        for(j =1;j<i;j++){
            array2[j] = array1[j-1]+array1[j];
        }
        array2[j] = 1;
        int *tmp;
        tmp = array1;
        array1 = array2;
        array2 = tmp;
    }   
    return array1;
}

算法步骤

  1. int* getRow(int rowIndex, int* returnSize) {

    • 定义了一个名为 getRow 的函数，它接受一个整数 rowIndex（表示要获取的Pascal三角形的行索引）和一个整数指针 returnSize（用于返回数组的大小）。

  2. int *array1 = (int*)malloc(sizeof(int)*(rowIndex+1));

    • 为第一行Pascal三角形分配内存，大小为 rowIndex+1。

  3. int *array2 = (int*)malloc(sizeof(int)*(rowIndex+1));

    • 为第二行Pascal三角形分配内存，大小同样为 rowIndex+1。

  4. *returnSize = rowIndex+1;

    • 设置 returnSize 的值为 rowIndex+1，表示返回数组的大小。

  5. int i,j;

    • 定义两个循环变量 i 和 j。

  6. array1[0] = 1;

    • 设置第一行的第一个元素为1。

  7. array2[0] = 1;

    • 设置第二行的第一个元素为1。

  8. for(i = 1;i<=rowIndex;i++){

    • 开始一个循环，从第2行开始，直到指定的 rowIndex 行。

  9. for(j =1;j<i;j++){

    • 对于每一行，从第2个元素开始，到该行的倒数第二个元素为止，计算该元素的值。

  10. array2[j] = array1[j-1]+array1[j];

    • 根据Pascal三角形的定义，当前元素的值是其上一行的两个相邻元素之和。

  11. array2[j] = 1;

    • 设置当前行的最后一个元素为1。

  12. int *tmp;

    • 定义一个临时指针 tmp。

  13. tmp = array1;

    • 将 array1 的地址赋给 tmp。

  14. array1 = array2;

    • 更新 array1 的地址为 array2 的地址。

  15. array2 = tmp;

    • 更新 array2 的地址为原来的 array1（即 tmp）的地址。

  16. return array1;

    • 返回最后一行的Pascal三角形。

总结

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(n)O(n)

线性递推

算法思想

​ 我们知道组合数的公式为Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n-m)!}，那么也就有Cnm−1=n!(m−1)!(n−m+1)!C_n^{m-1} = \frac{n!}{(m-1)!(n-m+1)!}。

两者相除你会得到关系式：Cnm=Cnm+1×n−m+1mC_n^m = C_n^{m+1} \times \frac{n-m+1}{m}。知道这些就好办了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
int* getRow(int rowIndex, int* returnSize) {
    *returnSize = rowIndex + 1;
    int* array = (int*)malloc(sizeof(int) * (rowIndex + 1));
    int i;
    array[0] = 1;
    for (i = 1; i <= rowIndex; i++) {
        array[i] = 1L * array[i - 1] * (1 + rowIndex - i) / i;
    }

    return array;
}

算法步骤

​ 这个函数就是套公式，其中要注意溢出问题，我在这里做了隐式强制转换，为了避免溢出。就是在int数前面乘上long的值，结果就会转换成long再附值给int。

总结

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(1)O(1)

136. 只出现一次的数字

题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

异或

算法分析

这道题要求时间复杂度O(n)O(n)，空间复杂度O(1)O(1)。

这里介绍一下异或：任何数和0异或都等于它本身，任何数和它自身异或都等于0。

代码实现

1
2
3
4
5
6
7
8
int singleNumber(int* nums, int numsSize) {
    int ret = nums[0];
    int i;
    for(i = 1;i<numsSize;i++){
        ret = nums[i]^ret;
    }
    return ret;
}

141. 环形链表

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if(head==NULL){
        return false;
    }
    struct ListNode* p = head->next;
    struct ListNode* q = head;
    int index = 0;
    int i;
    while(p!=NULL){
        for(i = 0;i<index;i++){
            if(q==p){
                return true;
            }
            q = q->next;
        }
        q = head;
        p = p->next;
        index++;
    }
    return false;
}

总结

该算法没有额外开辟空间所以空间复杂度为O(1)O(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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if(head==NULL||head->next==NULL) return false;
    struct ListNode* slow   = head;
    struct ListNode* fast  = head->next;
    while(slow!=fast){
        if(fast==NULL||fast->next==NULL){
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

总结

  • 空间复杂度O(1)O(1)
  • 时间复杂度粗略计算为O(n)O(n)

160. 相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

暴力解法

算法思想

​ 外层循环依次遍历，每一次遍历中依次遍历另一个链表如果有相等的节点则返回，如果没有那么整个外层函数会遍历完。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* p = headA;
    while(p!=NULL){
        struct ListNode *q = headB;
        while(q!=NULL){
            if(p==q){
                return p;
            }
            q = q->next;
        }
        p = p->next;
    }
    return NULL;
}

总结

时间复杂度为O(m∗n)O(m*n) ，空间复杂度为O(1)O(1)。

双指针

算法思想

​ 假设headA的长度为m,headB的长度为n,其中相交的长度为c，其中我们假设，m = a+c; n = b+c;两个链表以同样的速度前进，这里我们讨论a≠ba\neq b的情况，显然它们不能同时到达尾结点，那么当遍历完其中一个链表的时候我们改变它的指向，将它指向另一个链表的的头结点，这样它们一定会得到相同的节点，因为，如果两者有相交的点那么一定会在a+b+c次之前返回结果，如果没有相交的节点，则会同时到达尾结点。

代码实现

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA,
                                     struct ListNode* headB) {
    struct ListNode* p = headA;
    struct ListNode* q = headB;
    while (p != NULL && q != NULL) {
        if (p == q)
            return q;
        p = p->next;
        q = q->next;
        if (q == NULL && p != NULL)
            q = headB;
        if (p == NULL && q != NULL)
            p = headA;
    }
    return NULL;
}

算法步骤

  1. 初始化指针：p 指向 headA，q 指向 headB。
  2. 遍历链表：
    • 当 p 和 q 都不为 NULL 时，执行循环。
    • 如果 p 和 q 指向同一个节点，即 p == q，则返回该节点。
    • 否则，p 和 q 都向后移动一个节点。
  3. 处理链表长度不同的情况：
    • 如果 q 到达 NULL（即 headB 的末尾），而 p 还没有到达 NULL（即 headA 的末尾），则将 q 重新设置为 headA 的头节点，继续寻找相交节点。
    • 同理，如果 p 到达 NULL（即 headA 的末尾），而 q 还没有到达 NULL（即 headB 的末尾），则将 p 重新设置为 headB 的头节点，继续寻找相交节点。
  4. 返回结果：
    • 如果两个链表有相交节点，则最终 p 和 q 会指向同一个节点，并返回该节点。
    • 如果两个链表没有相交节点，则 p 和 q 会同时到达 NULL，并返回 NULL

总结

  • 时间复杂度为两个链表的总长O(m+n)O(m+n)
  • 空间复杂度为O(1)O(1)

168. Excel表列名称

题目描述

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

1
2
3
4
5
6
7
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

数学

算法思想

  1. 从右到左生成列标题：
    Excel的列标题是从A开始的，每26个字母之后重新开始（AA, AB, AC, …, AZ, BA, BB, …）。这意味着我们可以将给定的整数columnNumber视为一个26进制的数，其中每一位对应一个字母。例如，第27列是’AA’，因为27（十进制）= 1 * 26^1 + 1 * 26^0（二十六进制）。
  2. 计算每一位的字母：
    为了找到每一位对应的字母，算法使用取模运算（% 26）来得到当前位的值，并转换为对应的字母（通过加上’A’的ASCII值）。然后，算法通过整除（/ 26）来更新columnNumber，以便在下一次迭代中处理下一位。
  3. 反转字符串：
    由于算法是从右到左生成列标题的，所以生成的字符串需要反转，以便它与Excel中的列标题顺序相匹配。这是通过交换字符串的前半部分和后半部分来实现的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char* convertToTitle(int columnNumber) {
    char *ret = (char*)malloc(sizeof(char)*8);
    int length = 0;
    while(columnNumber!=0){
        int a = (columnNumber-1)%26+1;
        ret[length++] = a - 1+'A';
        columnNumber=(columnNumber-a)/26;
    }
    int mid = length/2;
    int i;
    for(i = 0;i<mid;i++){
        char tmp = ret[i];
        ret[i] = ret[length-1-i];
        ret[length-1-i] = tmp;
    }
    ret[length] = '\0';
    return ret;
}

算法步骤

  1. char *ret = (char*)malloc(sizeof(char)*8);

动态分配一个字符数组 ret，其大小为8。这个数组将用于存储转换后的Excel列标题。

  1. int length = 0;

初始化一个整数 length 用于跟踪 ret 数组中的字符数。

  1. while(columnNumber!=0){

使用循环，只要 columnNumber 不为0就继续。

  1. int a = (columnNumber-1)%26+1;

计算当前列的数字值（从1开始，因为Excel列从A开始）。例如，当 columnNumber 为27时，a 的值为1，表示这是第27列的第一个字符，即’A’。

  1. ret[length++] = a - 1+'A';

将当前字符添加到 ret 数组中，并增加 length 的值。这里 a - 1+'A' 是将数字值转换为相应的字符值。

  1. columnNumber=(columnNumber-a)/26;

更新 columnNumber，以便在下一次迭代中处理下一个字符。

  1. int mid = length/2;

计算 ret 数组的中间位置。

  1. int i;

定义一个循环变量 i。

  1. for(i = 0;i<mid;i++)

开始一个循环，从0到 mid-1。

  1. char tmp = ret[i];

交换 ret 数组的前半部分和后半部分，这是为了反转字符串，因为Excel列标题是从左到右读取的，但我们的算法是从右到左生成的。

  1. ret[i] = ret[length-1-i];

交换字符。

  1. ret[length-1-i] = tmp;

完成字符交换。

  1. ret[length] = '\0';

在字符串的末尾添加空字符，以确保它是一个有效的C字符串。

  1. return ret;

总结

时间复杂度

时间复杂度衡量的是算法执行所需的时间随输入规模增长的趋势。对于这个函数convertToTitle，输入规模可以认为是columnNumber的大小。

  • 计算列标题的每一位：这个部分通过一个while循环实现，循环的次数最多为columnNumber的位数，也就是log⁡26(columnNumber)\log_{26}(columnNumber)（因为每一位代表26进制的一个数字）。因此，这部分的时间复杂度是O(log⁡26(columnNumber))O(\log_{26}(columnNumber))。
  • 反转字符串：这个部分通过一个for循环实现，循环的次数是字符串长度的一半，即字符串长度除以2。由于字符串长度最多为8（这是ret数组的大小），这部分的时间复杂度是O(1)（常数时间复杂度）。

因此，整个算法的时间复杂度主要由while循环决定，即O(log⁡26(columnNumber))O(\log_{26}(columnNumber))。

空间复杂度

空间复杂度衡量的是算法执行过程中所使用的额外空间的大小。

  • 动态分配的内存：算法使用malloc分配了一个大小为8的字符数组ret来存储生成的列标题。这个空间的使用是固定的，不随输入规模变化，因此空间复杂度是O(1)。
  • 局部变量：算法中还使用了几个局部变量（如length、a、mid、i等），它们的空间使用是常数级别的，对空间复杂度没有影响。

因此，整个算法的空间复杂度是O(1)。

综上所述，该算法的时间复杂度是O(log⁡26(columnNumber))O(\log_{26}(columnNumber))，空间复杂度是O(1)。

169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

概率法

算法思想

很明显我们能知道多数出现的概率大于12\frac12，然后我们随机选择一个数来判断是否为多数，如果不是得话就再次随机选取一个判断是否为多数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int majorityElement(int* nums, int numsSize) {
    srand((unsigned int)time(NULL));
    int limit = numsSize/2;
    int cnt = 0;
    int i;
    while(1){
        int index  = rand()%numsSize;
        for(i = 0;i<numsSize;i++){
            if(nums[i] == nums[index]){
                cnt++;
            }
        }
        if(cnt>limit){
            return nums[index];
        }else{
            cnt=0;
        }
    }
    return false;
}

总结

该算法没有开辟新的空间所以空间复杂度为O(1)O(1)。

最差的时间复杂度为O(∞)O(\infty) ,当然这几乎是不可能发生的，这里我们来计算一下总共需要次数的期望估计值。我们假设ii是第ii次拿到多数，其中第ii次拿到多数的概率为12i\frac{1}{2^i}；其中期望为：

E(i)=∑i=1∞i×12i≈2E(i) = \sum^{\infty}_{i=1}i\times \frac{1}{2^i} \approx 2

之后的时间复杂度主要花费在判断上了，由于是依次判断所以时间复杂度为O(n)O(n)。

摩尔法

算法思想

​ 该算法的思想基于一个数学事实：如果一个数在数组中出现的次数超过数组长度的一半，那么遍历数组时，这个数将始终是当前的“候选主要元素”。这个算法通过维护一个候选主要元素和它的计数器来实现这一点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int majorityElement(int* nums, int numsSize) {
    int num = nums[0];
    int i;
    int cnt = 1;
    for (i = 1; i < numsSize; i++) {
        if (num == nums[i]) {
            cnt++;
        } else {
            cnt--;
            if (cnt < 0) {
                num = nums[i];
                cnt = 0;
            }
        }
    }
    return num;
}

算法步骤

  1. 初始化 num 为数组的第一个元素，cnt 为 1。num 是当前的候选主要元素，cnt 是该候选元素的出现次数。
  2. 从数组的第二个元素开始遍历（i = 1）。
  3. 如果当前的候选元素 num 与数组中的当前元素相同，则 cnt 增加 1。
  4. 如果当前的候选元素 num 与数组中的当前元素不同，则 cnt 减少 1。
  5. 如果 cnt 变为负数，这意味着当前的候选元素 num 不可能是主要元素，因为主要元素的出现次数必须超过数组长度的一半。因此，将 num 更新为当前的数组元素，并将 cnt 重置为 0。
  6. 遍历完成后，num 就是出现次数超过一半的主要元素。

总结

​ 这个算法的关键在于这样一个事实：如果有一个元素的出现次数超过了数组长度的一半，那么它一定是多数。

​ 这个算法的时间复杂度是 O(n)，其中 n 是数组的长度。

190. 颠倒二进制位

题目描述

颠倒给定的 32 位无符号整数的二进制位。

逐为颠倒

算法思想

我们很容易就能取到最低位的数，那么我们设置一个ret然后每一次都加上与原数据取余，之后在向左位移，由于是多少位你就移多少位就可以。

代码实现

1
2
3
4
5
6
7
8
9
10
11
uint32_t reverseBits(uint32_t n) {
    int i;
    uint32_t ret = 0;
    for(i = 0;i<31;i++){
        ret = ret+n%2;
        n = n>>1;
        ret = ret<<1;
    }
    ret+=n%2;
    return ret;
}

算法步骤

  1. 初始化一个变量ret为0，它将用于存储反转后的二进制数。
  2. 初始化一个循环计数器i，从0开始，因为我们需要处理的是从最低位（最右边的位）开始的每一位。
  3. 进入一个循环，该循环将运行32次（对于32位无符号整数来说）。然而，由于原始代码中的循环条件是i < 31，它实际上只处理了31位，忽略了最高位（符号位，对于uint32_t类型来说总是0）。
  4. 在循环的每次迭代中，执行以下步骤：
    a. 使用取模操作n % 2获取n的最低位（最右边的位）。
    b. 将这个最低位加到ret的最低位上，从而将其添加到反转后的结果中。
    c. 使用右移操作n >> 1将n的所有位向右移动一位，丢弃最低位，以便处理下一位。
    d. 使用左移操作ret << 1将ret的所有位向左移动一位，为下一位腾出空间。
  5. 循环结束后，ret将包含n的二进制表示的反转版本。然而，由于原始代码没有处理第32位（符号位），所以这一步实际上是不必要的。
  6. 返回ret作为结果。

总结

​ 这个算法的关键在于逐位处理输入整数的二进制表示，并通过位移和加法操作来构建反转后的结果。

205. 同构字符串

题目描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

双指针

算法思想

​ 该算法的思想是同时遍历两个字符串，该算法基于一个事实，如果两个字符串同型那么同时移动相等的字符和不相同的字符是同步的，这就两条相同的马路，平整的的地方和有坑的地方是对应的，所以我们就假设有两个人同时以相同的速度前进，如果两个人其中有一个掉坑了而另一个没有掉坑那么说明两个人走的道路不同。如果两个人都到终点了那就说明两条道路是相等的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isIsomorphic(char* s, char* t) {
    int length = strlen(s);
    int i,j;
    for(i = 0;i<length;i++){
        int s1 = s[i];
        int t1 = t[i];
        for(j = i+1;j<length;j++){
            if((s1==s[j]&&t1!=t[j])||
            (s1!=s[j]&&t1==t[j]))
            return false;
        }
    }
    return true;
}

算法步骤

  1. 遍历字符串：从字符串s的第一个字符开始，逐个字符向后遍历。
  2. 比较字符对：对于每个字符s[i]，与其后面的字符s[j]进行比较，其中j从i+1开始直到字符串的末尾。
  3. 检查同构关系：对于每一对字符(s[i], s[j])，检查它们与对应位置上的字符(t[i], t[j])在t中的出现情况。如果发现字符s[i]在s中与字符s[j]对应的t字符不同，或者字符t[i]在t中与字符t[j]对应的s字符不同，则说明不符合同构的条件。
  4. 返回结果：如果发现不同构的情况，则立即返回false；如果遍历完毕都没有发现不同构的情况，则返回true。

总结

​ 该算法的时间复杂度相对较高最差达到O(n2)O(n^2),当然最好的情况是O(1)O(1)，实际上同型的字符串还是很稀有的字符串越长那么同型出现的概率会越低的，所以该算法的时间复杂度不会太差，而且该算法的空间复杂度为O(1)O(1)这似乎也是一大亮点。至于为什么不用哈希表，答：我不会用。

219. 存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

哈希表

算法思想

  1. 遍历整个数组，对于数组中的每个元素，我们都计算它的哈希值。
  2. 使用哈希值将元素存储在哈希表中。
  3. 如果哈希表中已经存在相同值的元素，则检查它们的索引差是否不超过k。如果是，则返回true，否则继续遍历。
  4. 如果遍历完整个数组都没有找到满足条件的两个索引，则返回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
typedef struct Node{
    int index;
    int val;
    struct Node* next;
}Node;

#define HASH_SIZE 10000
Node* hash_table[HASH_SIZE];
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    for(int i = 0;i<HASH_SIZE;i++){
        hash_table[i] = NULL;
    }
    for(int i=0;i<numsSize;i++){
        int key = abs(nums[i])%HASH_SIZE;
        Node* tmp = hash_table[key];
        while(tmp!=NULL){
            if(nums[i]==tmp->val&&abs(tmp->index-i)<=k) return true;
            tmp = tmp->next;
        }
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->val = nums[i];
        new_node->index = i;
        new_node->next = hash_table[key];
        hash_table[key] = new_node;
        
    }
    return false;
}

算法步骤

  1. 哈希表的使用：代码中使用了一个哈希表来存储数组中的元素及其对应的索引。哈希表的大小为HASH_SIZE，默认为10000。这里选择了一个相对较大的素数作为哈希表的大小，以降低哈希冲突的概率。
  2. 哈希函数：通过取元素的绝对值并对哈希表大小取模，将元素映射到哈希表的索引位置。这种哈希函数在不同范围内的整数都能够较为均匀地映射到哈希表上。
  3. 处理哈希冲突：由于哈希表中的每个位置可能存储多个元素，因此使用了链表来处理哈希冲突。如果哈希表中已经存在相同值的元素，就会将新元素插入到链表的头部，而在查找时则需要遍历链表。
  4. 查找满足条件的索引对：在遍历数组的过程中，对于每个元素，都会计算其哈希值，并检查哈希表中是否已经存在相同值的元素。如果存在，则检查它们的索引差是否不超过k。如果满足条件，则返回true。否则，将当前元素及其索引插入到哈希表中，并继续遍历数组。

总结

​ 这种方法的时间复杂度是O(n)O(n)，因为在每次插入和查找元素时，哈希表的操作都是常数时间的。因此，整个算法的时间复杂度主要取决于遍历数组的时间复杂度，即O(n)O(n)。

222. 完全二叉树的节点个数

题目描述

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

通过高度递归计算

算法思想

由于完全二叉树的结构特点，我们可以分别求出左子树和右子树的高度，如果左子树的高度等于右子树的高度，则说明左子树是一棵满二叉树，其节点个数可以直接计算；否则，右子树是一棵满二叉树，其节点个数可以直接计算。然后递归地对另一棵子树执行相同的操作。

代码实现

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;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int get_height(struct TreeNode* root){
    if(root==NULL) return 0;
    int height = 0;
    while(root){
        height++;
        root= root->left;
    }
    return height;
}
int countNodes(struct TreeNode* root) {
    if(root==NULL) return 0;
    int left = get_height(root->left);
    int right = get_height(root->right);
    if(left==right){
        return (1<<left)+countNodes(root->right);
    }else{
        return (1<<right)+countNodes(root->left);
    }
}

算法步骤

  1. 计算左子树和右子树的高度： 算法首先需要计算左子树和右子树的高度。为此，它使用了一个名为 get_height 的辅助函数，该函数沿着左子树向下遍历，直到到达最底层，然后返回树的高度。
  2. 判断左子树是否是满二叉树： 然后算法比较左子树和右子树的高度。如果它们相等，则左子树是满二叉树，其节点数可以通过直接计算得到。
  3. 递归计算节点数： 如果左子树是满二叉树，则算法直接计算左子树的节点数，然后递归地对右子树执行相同的操作。如果右子树是满二叉树，则算法直接计算右子树的节点数，然后递归地对左子树执行相同的操作。
  4. 返回节点数： 当递归到叶子节点时，返回节点数为 0。然后，递归的返回值会累加起来，直到整棵树的节点数被计算出来。

总结

​ 这个算法用于计算完全二叉树的节点个数，其核心思想是利用完全二叉树的性质，通过递归地将问题分解成更小的子问题，从而实现了时间复杂度低于O(n)O(n) 和空间复杂度为 O(1)O(1)的目标。

257. 二叉树的所有路径

题目描述

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

深度优先

算法思想

使用深度优先遍历其中利用到了回溯思想，回溯思想大致意思就是判断下一步是否满足条件，如果满足则将结果返回给调用者，这里我们大概也能想到这是一个递归的过程。

该算法在使用一个数组来记录路径的节点，当访问到叶子节点的时候我们的主要任务就是拼接字符串。

代码实现

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void method(struct TreeNode* root,int *returnSize,char **str_arr,int *arr,int size){
     if(root!=NULL){
         if(root->left==NULL&&root->right==NULL){
             char *tmp = (char*)malloc(sizeof(char)*1024);
             int len = 0;
             for(int i = 0;i<size;i++){
                 len+= sprintf(tmp+len,"%d->",arr[i]);
             }
             sprintf(tmp+len,"%d",root->val);
             str_arr[(*returnSize)++] = tmp;
         }else{
             arr[size] = root->val;
             method(root->left,returnSize,str_arr,arr,size+1);
             method(root->right,returnSize,str_arr,arr,size+1);
         }
     }
 }
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    char **str_arr = (char**)malloc(sizeof(char*)*100);
    int arr[100]={0};
    method(root,returnSize,str_arr,arr,0);
    return str_arr;
}

算法步骤

  1. method 函数是一个递归函数，用于遍历二叉树节点，并生成路径字符串。它的参数包括根节点指针 root、返回路径数组的大小指针 returnSize、存储路径字符串的数组 str_arr、存储当前路径节点值的数组 arr、以及当前路径节点个数 size。
  2. 如果当前节点 root 不为空，则分两种情况讨论：
    • 如果当前节点是叶子节点（即没有左右子节点），则生成当前路径的字符串，并将其存储到 str_arr 数组中，同时更新 returnSize。
    • 如果当前节点不是叶子节点，则将当前节点的值加入到 arr 数组中，并递归调用 method 函数分别处理左右子树，注意递归调用时 size+1 表示路径节点个数增加。
  3. binaryTreePaths 函数是入口函数，负责初始化返回路径数组的大小指针 returnSize，创建存储路径字符串的数组 str_arr，以及存储当前路径节点值的数组 arr。然后调用 method 函数进行递归遍历，并返回最终的路径字符串数组。
  4. 返回的 str_arr 数组中存储的是指针，指向动态分配的字符串内存空间，这些字符串分别表示从根节点到叶子节点的路径。

总结

该算法的时间复杂度为O(n2)O(n^2)，空间复杂度为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
43
44
45
46
47
48
49
char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char** paths = (char**)malloc(sizeof(char*) * 1001);
    *returnSize = 0;
    if (root == NULL) {
        return paths;
    }

    struct TreeNode** node_queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1001);
    char** path_queue = (char**)malloc(sizeof(char*) * 1001);

    int left = 0, right = 0;

    char* tmp = malloc(sizeof(char) * 1001);
    sprintf(tmp, "%d", root->val);
    node_queue[right] = root;
    path_queue[right++] = tmp;

    while (left < right) {
        struct TreeNode* node = node_queue[left];
        char* path = path_queue[left++];

        if (node->left == NULL && node->right == NULL) {
            paths[(*returnSize)++] = path;
        } else {
            int n = strlen(path);
            if (node->left != NULL) {
                char* tmp = malloc(sizeof(char) * 1001);
                for (int i = 0; i < n; i++) {
                    tmp[i] = path[i];
                }
                sprintf(tmp + n, "->%d", node->left->val);
                node_queue[right] = node->left;
                path_queue[right++] = tmp;
            }

            if (node->right != NULL) {
                char* tmp = malloc(sizeof(char) * 1001);
                for (int i = 0; i < n; i++) {
                    tmp[i] = path[i];
                }
                sprintf(tmp + n, "->%d", node->right->val);
                node_queue[right] = node->right;
                path_queue[right++] = tmp;
            }
        }
    }
    return paths;
}

算法步骤

  1. 初始化
    • 分配一个足够大的数组paths用于存储最终的路径字符串。
    • 初始化returnSize为0，表示当前存储的路径数量。
    • 如果根节点为空，直接返回paths（此时它为空）。
  2. 队列初始化
    • 创建两个队列node_queue和path_queue，分别用于存储待处理的节点和对应的路径。
    • 创建临时字符数组tmp，用于构建路径字符串。
  3. 根节点入队
    • 将根节点的值转换为字符串，并添加到path_queue中。
    • 将根节点添加到node_queue中。
  4. 广度优先搜索
    • 当node_queue非空时，执行循环。
      • 从队列中取出一个节点和对应的路径。
      • 如果这个节点是叶子节点（即没有左右子节点），则将当前路径添加到paths数组中，并增加returnSize。
      • 否则，检查这个节点的左子节点和右子节点：
        • 如果左子节点存在，复制当前路径，并在末尾添加指向左子节点的箭头和左子节点的值，然后将左子节点和新的路径添加到队列中。
        • 如果右子节点存在，同样复制当前路径，添加指向右子节点的箭头和右子节点的值，并将右子节点和新的路径添加到队列中。
  5. 返回结果
    • 返回paths数组，其中包含了从根节点到所有叶子节点的路径。

总结

时间复杂度和空间复杂度均为O(n2)O(n^2)

290. 单词规律

题目描述

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

暴力解法

算法思想

对于模式字符串中的每个字符，将其映射到对应的单词。使用一个哈希表 hash_table 来存储模式字符到单词的映射关系。哈希表的索引为模式字符经过转换得到的小写字母的索引（‘a’ 到 ‘z’）。对于每个模式字符，如果对应的哈希表项为空，则将其指向当前单词；如果哈希表项不为空，则检查当前单词是否与哈希表项指向的单词相同，若不同则说明不满足模式，返回 0。检查是否有重复的单词映射到不同的模式字符，如果存在，则说明不满足。如果所有模式都映射成功且没有重复映射，则说明满足模式。

代码实现

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
#define MAX_LEN 1000
typedef struct Node{
    char* str;
}Node;
bool wordPattern(char* pattern, char* s) {
    int p_len = strlen(pattern);
    char *words[MAX_LEN] = {NULL};
    int w_count = 0;
    Node hash_table[26];
    for(int i = 0;i<26;i++){
        hash_table[i].str = NULL;
    }
    // 分割字符串s为单词数组
    char *token = strtok(s, " ");
    while (token != NULL) {
        words[w_count++] = token;
        token = strtok(NULL, " ");
    }

    if (p_len != w_count)
        return 0; // 如果单词数量不匹配，则返回0

    for(int i = 0;i<p_len;i++){
        if(hash_table[pattern[i]-'a'].str==NULL){
            hash_table[pattern[i]-'a'].str = words[i];
        }else{
            if(strcmp(words[i],hash_table[pattern[i]-'a'].str)) return 0;
        }
    }
    for(int i = 0;i<26;i++){
        for(int j = i+1;j<26;j++){
            if(hash_table[i].str!=NULL&&hash_table[j].str!=NULL)
                if(!strcmp(hash_table[i].str,hash_table[j].str)) return 0;
        }
    }
    return 1; // 所有映射都匹配，则返回1
}

算法步骤

  1. 定义了一个结构体 Node 用于表示哈希表中的节点，其中包含一个指向字符串的指针 str。
  2. 使用了哈希表 hash_table，其大小为 26，因为假设 pattern 中的字符仅为小写字母。哈希表的索引通过将字符映射到对应的小写字母（‘a’ 到 ‘z’）来实现。
  3. 使用 strtok 函数将输入字符串 s 按空格分割成单词，并将它们存储在 words 数组中。
  4. 然后比较 pattern 和 words 数组中的单词，通过哈希表来建立模式和单词之间的映射关系。如果某个模式字符对应的哈希表项为空，则将其指向当前单词；如果哈希表项不为空，则检查当前单词是否与哈希表项指向的单词相同，若不同则返回 0。
  5. 检查是否有重复的单词映射到不同的模式字符，如果存在，则返回 0。
  6. 如果所有模式都映射成功且没有重复映射，则返回 1。

总结

这个算法的时间复杂度主要取决于字符串分割和哈希表的操作。分割字符串的时间复杂度为 O(n)O(n)，其中 n 为字符串长度。建立模式与单词之间的映射以及检查是否存在重复映射的操作，时间复杂度为 O(n)O(n)，因为哈希表的大小固定为 26。因此，总体时间复杂度为$ O(n)$。