0


101道算法JavaScript描述【二叉树】9

在这里插入图片描述

🐧主页详情:一名不会打字的程序员~的个人主页
📢作者简介:🏅物联网领域创作者🏅 and 🏅阿里专家博主🏅 and 🏅华为云享专家🏅
✍️人生格言:最慢的步伐不是跬步,而是徘徊;最快的脚步不是冲刺,而是坚持。
🧑‍💻人生目标:成为一名合格的程序员,做未完成的梦:实现财富自由。
🚩技术方向:NULL
👻如果觉得博主的文章还不错的话,请三连支持一下博主哦
💬给大家介绍一个我一直在用的求职刷题收割offe👉点击进入网站
在这里插入图片描述

文章目录

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

示例1

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例2

输入: coins = [2], amount = 3
输出: -1

解法一 动态规划法

思路

  1. 由于需要找到最少的硬币,所以需要列举出所有可能的结果(如题)
  2. 要凑够 amount 元硬币,可以从最 i -> amount 之前进行枚举 (counter) (下列出 最少次数)amount = 1; counter[1] = 1 coins[1] = 1amount = 2; counter[2] = 1 coins[2] = 2amount = 3; counter[3] = 2 coins[1] + coins[2]amount = 4; counter[4] = 2 coins[2] + coins[2]amount = 5; counter[5] = 3 coins[2] + coins[2] + coins[1]amount = 6; counter[6] = 3 coins[2] + coins[2] + coins[2]amount = 7; counter[7] = 2 coins[5] + coins[2]amount = 8; counter[8] = 3 coins[5] + coins[2] + coins[1]amount = 9; counter[9] = 3 coins[5] + coins[2] + coins[2]amount = 10; counter[10] = 2 coins[5] + coins[5]amount = 11; counter[11] = 1 coins[5] + coins[5] + coins[1]
  3. 递增 i 并且记录下 能组合成 i 的 硬币数量 counter[i]
  4. 遍历 coins 数组,从 counter 中找到对应剩余金额(i - coins[j])的最小次数 + 1

详解

  1. 需要计算出每一步的最佳次数,因此可以将每一步的次数保存在 counter 数组中
  2. counter中每一项的最大值应该是 amount / 1 次,此处默认填充 (amount / 1) + 1 次
  3. 遍历amoount 数组 依次递增,在 coins 数组中找到满足 i 的最少硬币数,保存在 counter 中
  4. 若 counter[i] 已经保存有最少的值,比较此次计算的最小次数,取两者较小
  5. 重复 3,4 步骤 直到 amount 遍历结束
constcoinChange=(coins, amount)=>{const counter =Array(amount +1);
  counter.fill(amount +1);
  counter[0]=0;for(let i =1; i <= amount; i ++){for(let j =0; j < coins.length; j ++){if(i - coins[j]>=0){// i - coins[j] 能凑成 i 的上一步的 最小硬币数量
        counter[i]= Math.min(counter[i], counter[i - coins[j]]+1);}}}// 最坏结果应该是 counter[amount] = amountreturn counter[amount]> amount ?-1: counter[amount];}

复杂度分析

  • 时间复杂度:O(Sn)O(Sn)时间复杂度是 O(Sn)O(Sn),S是 amount大小,需要迭代 Sn
  • 空间复杂度:O(S)O(S)每次迭代时没有增加新的资源,O(1)O(1)

解法二 递归

思路

由于要获取最小奖金币次数,实质上就是能拿到的满足 amount 的面值尽可能大的银币的个数。例如:

coins = [11, 12, 5, 3] amount = 121;

则次数刚好是 121 / 11 = 11,其他的取法均大于 11 次。

若 amount = 124 则有次数 (121 / 11) + (3 / 3) = 12次

另外,在考虑最多次数时,应当满足有 amount / 1 = amount 次。

详解

  1. amount 是总金额,要用最少的硬币数,应当是从最大的硬币开始拿起
  2. 大的硬币可以多次拿取,就有 amount % coins[i] === 0 成立
  3. 可以保存一个最少硬币数 mincounter 的状态,按coins数组最大的开始,依次向最小的硬币循环
  4. 按照可以使用的最大硬币次数作为循环起始条件,依次减1直至为0,递归调用
  5. 当剩余 amount / coins[n] > 当前次数 + mincounter 则直接退出循环
  6. 当amount为0时,即可得到最优结果
const coinChange =(coins, amount)=>{// 假设 最少次数 最多不会超过 amount 次
  let minCount = amount +1;
  let coinsTemp = coins.sort((a, b)=> b - a);// 防止有超过 amount 面值的硬币出现const maxValueIndex = coinsTemp.findIndex(v => v <= amount);// 已经计算的次数,剩余的金额,coins,当前硬币位置const calculateCountes =(count, amount, coins, index)=>{if(amount ===0){if(count < minCount){// 每次递归的所有可能结果进行保存
        minCount = count;}return;}
    let maxCountatIndex =parseInt((amount / coins[index]),10);// 执行到超出数组边界 或者 预计最小次数大于已有 minCount 时 直接退出递归if((index === coins.length)|| maxCountatIndex + count >= minCount){return;}// amount 最少是 amount / coins[index] 次 coins[index] 的 和for(let j = maxCountatIndex; j >=0; j --){// 累计次数,剩余amount,银币数组,到达的coins数组下标calculateCountes(count + j, amount -(coins[index]* j), coins, index +1);}}calculateCountes(0, amount, coinsTemp, maxValueIndex);return minCount === amount +1?-1: minCount;}

复杂度分析

  • 时间复杂度:O(Sn)O(Sn)
  • 空间复杂度:O(n)O(n)nn 为递归调用的最大深度,即需要 O(n)O(n) 空间的递归堆栈。

跳跃游戏

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1:

输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2:

输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

方法一 贪心算法

思路

贪心算法的思路就是每到一个位置,都跳跃到当前位置可以跳跃的最大距离。当最后跳跃的最远距离等于或大于最后一个位置的时候,我们就认为可以到达最后一个位置,返回true

详解

  1. 首先我们初始化最远位置为0,然后遍历数组;
  2. 如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置;
  3. 每次都去比较当前最远位置和当前数组下标,如果最远距离小于等于当前下标就返回false。
constcanJump=function(nums){let max =0;// 跳到最远的距离for(let i =0; i < nums.length -1; i +=1){// 找到能跳的最远的的距离if(i + nums[i]> max){
      max = i + nums[i];}// 如果跳的最远的小于当前脚标,返回falseif(max <= i){returnfalse;}}returntrue;};

复杂度分析

  • 时间复杂度:O(n)O(n)只需要访问 nums 数组一遍,共 nn 个位置,nn 是 numsnums 数组的长度。
  • 空间复杂度:O(1)O(1)在 max 变量分配内存情况下,内存不会随着遍历有增长趋势,不需要额外的空间开销。

方法二 动态规划

思路

我们遍历数组,每到一个点 i,我们就去判断是否可以到达当前点;如果可以,就记录

true

,否则为

false

,最后判断 是否可以到达(nums.length - 1);

详解

  1. 遍历数组 nums,每到一个点 i,我们就判断时刻可以到达当前点;
  2. 如果 i 之前某点 j 本身是可以到达的,并且与当前点可达,表示点 i 是可达的;
  3. 我们遍完成后,直接判断(nums.length - 1)是否可以达到。
constcanJump=function(nums){// 定义一个数组,用来记录nums的点是否是可以达到的const list =[nums.length];// 遍历numsfor(let i =1; i < nums.length; i++){// 遍历listfor(let j =0; j < i; j++){// 如果j点是可以到达的,并且j点是可以达到i点的// 则表示i点也是可以达到的if(list[j]&& nums[j]+ j >= i){
        list[i]=true;// 如果i点可以达到,则跳出当前循环break;}}}return list[nums.length -1];};

复杂度分析

  • 时间复杂度:O(n^2)O(n2) 对于每个元素,通过两次遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n^2)O(n2) 的时间
  • 空间复杂度:O(n)O(n) 对于每次循环都需要给 j 重新分配空间,所以空间复杂度 O(n)O(n)

方法三 回溯

思路

我们模拟从第一个位置跳到最后位置的所有方案。从第一个位置开始,模拟所有可以跳到的位置,然后判断当前点是否可以到达(nums.length - 1);当没有办法继续跳的时候,就回溯。

详解

  1. 我们每次传入一个下标 p,并且判断 p 是否可以达到最后的下标;
  2. 如果传入的 p 等于(nums.length - 1),则表示可以到达,如果不行,则继续循环判断;
  3. 如果存在 p 等于 (nums.length - 1),则返回 true,不存在则返回 false
constcanJump=function(nums){returncheckJumpPosition(0, nums);;};functioncheckJumpPosition(p, nums =[]){// 定义p点可以到达的最远距离let jump = p + nums[p];// 如果p点可以到达nums.length - 1,则返回trueif(p === nums.length -1){returntrue;}// 如果最远距离大于(nums.length - 1),我们就将(nums.length - 1),设为最远距离if(p + nums[p]> nums.length -1){
    jump = nums.length -1;}// 我们从p + 1开始到最远距离中间,找到(nums.length - 1)// 如果可以,则返回true,找不到则返回falsefor(let i = p +1; i <= jump; i +=1){if(checkJumpPosition(i, nums)){returntrue;}}returnfalse;}

复杂度分析

  • 时间复杂度:O(2^n)O(2n) 因为从第一个位置到最后一个位置的跳跃方式最多有 2^n 种,所以最多的耗时是 O(2^n)O(2n)
  • 空间复杂度:O(n)O(n) 对于每次循环都需要给 ii 重新分配空间,最大的长度是 nums.length,所以空间复杂度 O(n)O(n)

不同路径、Longest Increasing Subsequence和单词拆分

不同路径

一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,问总共有多少条不同的路径?

示例 1

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2

输入: m = 7, n = 3
输出: 28

思路

A B C D
E F G H

从点 (x = 0,y = 0)(x=0,y=0) 出发,每次只能向下或者向右移动一步,因此下一点的坐标为(x + 1, y)(x+1,y) 或者(x, y + 1)(x,y+1),一直到(x = m, y = n)(x=m,y=n)。在上图中,H 只能从 G 或者 D 达到,因此从 A 到 H 的路径数等于从 A 到 D 的路径与从 A 到 G 的路径之和。得出路径数量 T(m, n) = T(m-1, n) + T(m, n-1)T(m,n)=T(m−1,n)+T(m,n−1)。

我们又发现,当

    m
   
   
    =
   
   
    1
   
  
  
   m = 1
  
 
m=1 或 

 
  
   
    n
   
   
    =
   
   
    1
   
  
  
   n = 1
  
 
n=1 时(只能一直往下或往右走),路径数量为1,这里得出跳出递归的条件。

方法一 递归

详解

由上面的分析可得,到达 (m, n)(m,n)的路径数量为 (m, n-1)(m,n−1)坐标的路径数量与 (m-1, n)(m−1,n)坐标的路径数量之和 。可以使用最简单粗暴的递归方法

代码

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */constuniquePaths=function(m, n){if(m ===1|| n ===1){return1;}returnuniquePaths(m -1, n)+uniquePaths(m, n -1);};

方法二 动态规划

详解

根据以上思路,可以推出状态转移方程为

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]dp[i][j]=dp[i−1][j]+dp[i][j−1]
1111111123456713610152128
代码

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */constuniquePaths=function(m, n){const dp =newArray(m);for(let i =0; i < m; i++){
    dp[i]=newArray(n);}for(let i =0; i < m; i++){for(let j =0; j < n; j++){if(i ===0|| j ===0){
        dp[i][j]=1;}else{
        dp[i][j]= dp[i -1][j]+ dp[i][j -1];}}}return dp[m -1][n -1];};

复杂度分析

  • 时间复杂度: O(m * n)O(m∗n)

上述解法中,对 mm 和 nn 进行了双重循环,时间复杂度跟数字的个数线性相关,即为 O(m*n)O(m∗n)

  • 空间复杂度: O(m * n)O(m∗n)

申请了大小为 m * nm∗n的二维数组

方法三 动态规划优化

减少空间复杂度

详解

我们观察表格发现,下一个值等于当前值加上一行的值,利用这个发现,可以来压缩空间,用一维数组来实现

constuniquePaths=function(m, n){const dp =newArray(n).fill(1);for(let i =1; i < m; i++){for(let j =1; j < n; j++){
      dp[j]= dp[j -1]+ dp[j];}}return dp[n -1];};

复杂度分析

  • 时间复杂度: O(m * n)O(m∗n)
  • 空间复杂度:O(n)O(n)

方法四 排列组合

详解

其实这是个高中数学问题。因为机器人只能向右或者向下移动,那么不论有多少中路径,向右和向下走的步数都是一样的。当 m = 3,n = 2 m=3,n=2 时,机器人向下走了一步,向右走了两步即可到达终点。所以我们可以得到

路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数,转化为排列组合问题

不包括起点和终点,共移动 N = m + n - 2N=m+n−2,向右移动K = m - 1K=m−1,将 NN 和 KK 代入上述公式,可得

因此得出答案 C_{m + n -2}^{m - 1}Cm+n−2m−1

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */constuniquePaths=function(m, n){constN= m + n -2;constK= n -1;let num =1;for(let i =1; i <=K; i++){
    num = num *(N-K+ i)/ i;}return num;};

复杂度分析

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

Longest Increasing Subsequence

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

方法一 动态规划

思路

  • 状态定义:res[i] 表示以 nums[i] 为当前最长递增子序列尾元素的长度
  • 转移方程:通过方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1),动态计算出各上升子序列的长度。
  • 倒序取值:res 数组进行倒序,第一个即为最大长度的值。

详解

  1. 如果给定数组长度小于等于 1,则最长上升子序列的长度等于数组长度。
  2. 初始化一个长度等于给定数组的长度,且元素都为 1 的数组 res。
  3. 当 nums[i] > nums[j] 时,nums[i] 可以作为前一个最长的递增子序列 res[j] 新的尾元素,而组成新的相对于 res[i] 能够拼接的更长的递增子序列 res[i] = res[j] + 1,因为新的 res[i] 能够拼接的最长长度取决于 nums[i] 这个新的尾元素,而这个 nums[i] 不一定大于 nums[j],所以也不一定大于 res[j],那么在 i ~ j 之间,最大的递增子序列为 Max(res[i], res[j]+1);当 nums[i] <= nums[j],长度为元素本身,即为 1。所以得出方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1),通过转移方程收集各上升子序列的长度。
  4. 通过 sort 函数对 res 倒序排列,第一元素值 res[0] 就是最长的上升子序列长度。
/**
 * @param {number[]} nums
 * @return {number}
 */constlengthOfLIS=function(nums){const len = nums.length;if(len <=1){return len;}// 初始化默认全为1const res =newArray(len).fill(1);for(let i =1; i < len; i++){for(let j =0; j < i; j++){// 转移方程
      res[i]= Math.max(res[i], nums[i]> nums[j]? res[j]+1:1);}}// 倒序
  res.sort((a, b)=> b - a);return res[0];};

复杂度分析

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

方法二 二分查找

思路

  • 当前遍历元素大于前一个递增子序列的尾元素时(nums[i] > tail[end]),将当前元素追加到 tail 后面,这里解法其实和方法一中nums[i] > nums[j] 的解法一样。
  • 当 nums[i] <= tail[end] 时,寻找前一个递增子序列第一个大于当前值的元素,替换为当前值,查找用二分,最后左边的元素即为查找到的需要被替换的结果元素。

详解

1、如果给定数组长度小于等于 1,则最长上升子序列的长度等于数组长度。 2、初始化一个长度等于给定数组的长度,且第一个元素值等于给定数组的第一个元素值的数组 tail,tail 用来存储最长递增子序列的元素。 3、循环给定的数组,当前遍历元素大于前一个递增子序列的尾元素时(nums[i] > tail[end]),将当前元素追加到 tail 后面,这里解法 其实和方法一中nums[i] > nums[j] 的解法一样;当 nums[i] <= tail[end] 时,寻找前一个递增子序列第一个大于当前值的元素,替换为当前值,查找用二分,最后左边的元素即为查找到的需要被替换的结果元素。 4、循坏完之后,end + 1 即为最长的上升子序列长度。

/**
 * @param {number[]} nums
 * @return {number}
 */constlengthOfLIS=function(nums){const len = nums.length;if(len <=1){return len;}const tail =newArray(len);
  tail[0]= nums[0];let end =0;for(let i =1; i < len; i++){if(nums[i]> tail[end]){
      end +=1;
      tail[end]= nums[i];}else{let left =0;let right = end;// 二分查找while(left < right){// 位运算,右移一位const mid = left +((right - left)>>1);if(tail[mid]< nums[i]){
          left = mid +1;}else{
          right = mid;}}
      tail[left]= nums[i];}}return end +1;};

复杂度分析

  • 时间复杂度:O(nlogN)O(nlogN)外层一个数组循环遍历,里面嵌套一个二分查找,所以是 O(nlogN)O(nlogN)
  • 空间复杂度:O(n)O(n)创建的数组 tail 占用空间大小为 n,循环遍历中并没有分配新的空间

单词拆分

示例

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。
  • 注意你可以重复使用字典中的单词。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]  
输出: true  
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]  
输出: true  
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]  
输出: false

方法一 暴力破解法

思路

把字符串

s

的前缀从短到长拆出来进行判断是否在单词字典中,若在字典中则把前缀截取掉继续递归,直到字符串的长度为 0。在递归中若遇到字符串任何长度的前缀都无法匹配到字典中的单词,则回溯到上层递归。

详解

1、检查字典中是否有字符串的前缀; 2、若有的话,将字符串去掉这个前缀后继续遍历,重复步骤 1、2; 3、若某次调用发现整个字符串都已拆分并且都在字典内则返回 true;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-21YkVzx9-1659870334689)(https://3811097299-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5_VgO7Aapcy5begC-C%2F-M6-I6m57X_LoOQxykgn%2F-M6-IbJwjVrcOtj76ywA%2Fimage.png?alt=media&token=e18dc987-f918-4880-9248-68395d352aea)]

constwordBreak=function(s, wordDict){if(s.length ===0){returntrue;}for(let i =0; i < wordDict.length; i +=1){const startIndex = s.indexOf(wordDict[i]);if(startIndex ===0){// 将字符串去掉这个匹配到的前缀后继续遍历const temp = s.slice(startIndex + wordDict[i].length);if(wordBreak(temp, wordDict)===true){returntrue;}}}returnfalse;};
  • 时间复杂度:最坏情况下是 O(n^n)O(nn),因为考虑 s = 'aaaaaaaaaaaaaaaa', wordDict = ['a'],每一个字符都在字典中,此时递归的时间复杂度会达到 O(n^n) O(nn),妥妥超时
  • 空间复杂度:O(1)O(1),循环中申请了 3 个临时变量,与输入的字符串的长度无关,空间占用属于常数阶,故空间复杂度为 O(1)O(1)。

方法二 动态规划

思路

dp[i]

表示字符串

s

从开始到

i

位置是否可以由

wordDict

组成。使用

j

从头开始遍历,若

dp[i]

可由

wordDict

组成,并且

i

j

之间的单词可以在

wordDict中找到

,则说明

dp[i] = true

详解

1、第一层遍历:用 i 从头到尾遍历字符串; 2、第二层遍历:用 j 从头到 i 遍历字符串; 3、若

dp[j] = true

而且字典中存在字符串

s[i~j]

,则说明

dp[i] = true

; 4、继续步骤 1、2,直到整个字符串都遍历一遍; 5、若

dp[s.length()] = true

,则说明字符可由字段中的单词组合而成;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CoPFRWQl-1659870334693)(https://3811097299-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5_VgO7Aapcy5begC-C%2F-M6-I6m57X_LoOQxykgn%2F-M6-Ie1OD-shJ9PPcnsE%2Fimage.png?alt=media&token=0d6c4555-cbba-48e9-8f4c-30565a75e7a8)]

代码

constwordBreak=function(s, wordDict){const len = s.length;const dp =newArray(len +1).fill(false);
  dp[0]=true;for(let i =1; i <= len; i++){for(let j =0; j < i; j++){if(dp[j]&& wordDict.includes(s.substring(j, i))){
        dp[i]=true;break;}}}return dp[len];};

复杂度分析

  • 时间复杂度:O(n^2)O(n2)因为有两层循环,每层循环都从头遍历到尾。
  • 空间复杂度:O(n)O(n)因为只开辟了一个 nn长度的数组。

方法三 动态规划(优化版)

思路

第二层遍历中不用每次遍历

i

的长度,只要遍历字典中最长单词的长度

maxStep

即可。

详解

1、第一层遍历:用

i

从头到尾遍历字符串; 2、第二层遍历:用

j

i - maxStep

i

遍历字符串; 3、若

dp[j] = true

而且字典中存在字符串

s[i~j]

,则说明

dp[i] = true

; 4、继续步骤 1、2,直到整个字符串都遍历一遍; 5、若

dp[s.length()] = true

,则说明字符可由字段中的单词组合而成;

constwordBreak=function(s, wordDict){const len = s.length;const dp =newArray(len +1).fill(false);
  dp[0]=true;// 计算单词的最长长度let maxStep =0;for(let i =0; i < wordDict.length; i++){if(wordDict[i].length > maxStep){
      maxStep = wordDict[i].length;}}for(let i =1; i <= len; i++){const startOfJ = i - maxStep >0? i - maxStep :0;for(let j = startOfJ; j < i; j++){if(dp[j]&& wordDict.includes(s.substring(j, i))){
        dp[i]=true;break;}}}return dp[len];};

复杂度分析

  • 时间复杂度:O(n^2)O(n2)因为有两层循环,每层循环都从头遍历到尾。
  • 空间复杂度:O(n)O(n)因为最长只开辟了一个 nn 长度的数组。

本文转载自: https://blog.csdn.net/weixin_51568389/article/details/126215555
版权归原作者 一名不会打字的程序员 所有, 如有侵权,请联系我们删除。

“101道算法JavaScript描述【二叉树】9”的评论:

还没有评论