递归三元递归函数和参数递归终止条件递归单级搜索逻辑递归伪代码模板：函数recursion(level,param1,param2,...){//递归终止条件if(level>MAX_LEVEL){//输出结果return;}//处理当前层process_data(level,data,...);//进入下一层递归(level+1,p1,...);//resetstatereverse_state(level);}什么是分治法：分治法会将一个大问题拆解成小问题，拆解到最小的问题后，开始不断合并结果，递归是分治法的一种形式分治实施或分治实施的一部分，分治包括三个部分，分解，计算，合并。分而治之的场景有很多，比如快速排序和归并排序。分而治之伪代码模板：functiondivide_conquer(problem,param1,param2,...){if(problem===null){//返回结果}//除法问题subproblem=split_problem(problem,data)//计算器问题subResult1=divide_conquer(subproblem[0],p1,...)subResult2=divide_conquer(subproblem[1],p1,...)subResult3=divide_conquer(subproblem[2],p1,...)...结果=process_resule(subResult1,subResult2,subResult3,...)}实例计算n！n！=1*2*3...*nfunctionfactorial(n){如果(n<=1)返回1;returnn*factorial(n-1);}factorial(6);6*factorial(5);6*5*factorial(4);//...6*5*4*3*2*factorial(1);6*5*4*3*2*1;6*5*4*3*2;//...6*120;720;斐波那契数列，F(n)=F(n-1)+F(n+2)functionfib(n){if(n===0||n===1){returnn;}returnfib(n-1)+fib(n-2);}53.maxSubsequencesum(easy)给你一个整数数组nums，请找一个和最大的连续子数组（该子数组至少包含一个元素），并返回其最大总和。子数组是数组的连续部分。示例1：输入：nums=[-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组[4,-1,2,1]最大值之和,为6。示例2：输入：nums=[1]输出：1示例3：输入：nums=[5,4,-1,7,8]输出：23提示：1<=nums.length<=105-104<=nums[i]<=104Advanced：如果你已经实现了复杂度为O(n)的解决方案，请尝试使用更微妙的分而治之的解决方案。方法一：动态规划思想：当前最大子序列和只和之前的子序列和有关，循环数组，不断更新最大子序列复杂度：时间复杂度O(n)，空间复杂度O(1)js:varmaxSubArray=function(nums){constdp=[];letres=(dp[0]=nums[0]);//初始化状态for(leti=1;i0){//如果前一个状态是正数，则加上dp[i]+=dp[i-1];}res=Math.max(res,dp[i]);//更新最大值}returnres;};//状态压缩varmaxSubArray=function(nums){letpre=0,maxAns=nums[0];nums.forEach((x)=>{pre=Math.max(pre+x,x);maxAns=Math.max(maxAns,pre);});返回最大答案；}；方法二、分而治之的思路：一直划分，直到每个第一部分是一个数，然后不断合并，返回左右，左右合并后，取最大的三个子序列求和复杂度：时间复杂度O(nlogn)，二进制复杂度O(logn)，二进制后每层统计、左右、合并后的最大子序列和复杂度为O(n)，所以后续复杂度为O(nlogn)。空间复杂度O(logn)，递归栈空间，因为一分为二，每次数据大小减半js:functioncrossSum(nums,left,right,mid){if(left===right){//左右相等返回左边的值returnnums[left];}letleftMaxSum=Number.MIN_SAFE_INTEGER;//左最大值初始化letleftSum=0;for(leti=mid;i>=left;--i){leftSum+=nums[i];leftMaxSum=Math.max(leftMaxSum,leftSum);//更新左最大子序列和}letrightMaxSum=Number.MIN_SAFE_INTEGER;让rightSum=0;for(leti=mid+1;i<=right;++i){rightSum+=nums[i];rightMaxSum=Math.max(rightMaxSum,rightSum);//更新右边的最大子序列和}returnleftMaxSum+rightMaxSum;//返回左右合并后的最大子序列和}function_maxSubArray(nums,left,right){if(left===right){//递归终止条件returnnums[left];}constmid=Math.floor((左+右)/2);constlsum=_maxSubArray(nums,left,mid);//左最大子序列和constrsum=_maxSubArray(nums,mid+1,right);//右最大子序列和constcross=crossSum(nums,left,right,mid);//左右合并后的最大子序列andreturnMath.max(lsum,rsum,cross);//返回3中最大的子序列和}varmaxSubArray=function(nums){return_maxSubArray(nums,0,nums.length-1);};50.pow(x,n)(medium)实现pow(x,n)，即计算x的整数幂函数（即xn）例1：输入：x=2.00000,n=10输出：1024.00000例2：输入：x=2.10000,n=3输出：9.26100示例3：输入：x=2.00000,n=-2输出：0.25000解释：2-2=1/22=1/4=0.25提示：-100.0>>=1;//进行无符号右移1位，这里不能使用有符号右移(>>)//当n为-2^31时，转为正数计数时的二进制数为“100000000000000000000000000000000”,//如果有符号右移使用shift时，最左边的数将作为符号(1)，所以返回结果为-1073741824/*C++中只有一个右移运算符——>>。其定义如下：丢弃移出的低位；如果是无符号数，高位加0；如果是有符号数，则在高位加上符号位。JavaScript中有两个右移运算符——>>和>>>。其中>>是有符号右移，即高位补符号位（可能会出现负数变正数，正数变负数的异常情况）；>>>为无符号右移，高位不补0。*/}returnresult;}124、二叉树中的最大路径和（硬）路径定义为从中任意节点开始的序列树，遵循父节点-子节点连接，并到达任何节点。同一个节点在一个路径序列中最多出现一次。该路径至少包含一个节点，不一定经过根节点。路径和是路径中每个节点的值之和。给定二叉树的根节点root，返回其最大路径sum。示例1：输入：root=[1,2,3]输出：6解释：最优路径为2->1->3，路径和为2+1+3=6示例2：输入：root=[-10,9,20,null,null,15,7]输出：42解释：最优路径为15->20->7，路径和为15+20+7=42提示：取值范围树的节点数为[1,3*104]-1000<=Node.val<=1000方法一、递归思想：从根节点开始递归，每次递归分为三种情况：向左走，向右走，并且不动，用当前节点加上左右孩子树的最大路径，不断更新最大路径和复杂度：时间复杂度O(n)，n是树的节点数。空间复杂度O(n)，递归深度，最坏情况下的节点数js:constmaxPathSum=(root)=>{letmaxSum=Number.MIN_SAFE_INTEGER;//初始化最大路径和constdfs=(root)=>{if(root==null){//遍历节点为nullreturn0return0;}constleft=dfs(root.left);//递归左子树最大路径andconstright=dfs(root.right);//递归右子树的最大路径和maxSum=Math.max(maxSum,left+root.val+right);//更新最大值//返回当前子树分为左、右、不动3种情况的路径和constpathSum=root.val+Math.max(0,left,right);返回路径总和<0？0：路径总和；};dfs（根）；返回最大值；};169.大多数元素（简单）给定一个大小为n的数组nums，返回其中的大多数元素。众数元素是数组中出现次数超过?n/2?的元素。您可以假设数组是非空的，并且给定数组中的元素总是占多数。示例1：输入：nums=[3,2,3]输出：3示例2：输入：nums=[2,2,1,1,1,2,2]输出：2提示：n==nums.length1<=n<=5*104-109<=nums[i]<=109进阶：尝试设计一个时间复杂度O(n)、空间复杂度O(1)的算法来解决这个问题。方法一、排序思路：对数组进行排序，如果有一个数出现的次数比n/2多，那么这个数就在数组中nums.length/2的位置。复杂度分析：时间复杂度：O(nlogn)，快速排序时间复杂度。空间复杂度：O(logn)，排序需要logn空间复杂度js:varmajorityElement=function(nums){nums.sort((a,b)=>a-b);返回nums[Math.floor(nums.length/2)];};方法二、哈希表思路：循环数组，用哈希表存储数字和对应的数字，如果数字出现的个数大于n/2，则返回这个数字复杂度分析：时间复杂度：O(n),n是nums数组的长度。空间复杂度：O(n)，哈希表需要的空间js:varmajorityElement=function(nums){lethalf=nums.length/2;让对象={};for(letnumofnums){obj[num]=(obj[num]||0)+1;if(obj[num]>half)返回num；}};方法三：offsetjs://[1,1,2,2,2]constmajorityElement=nums=>{letcount=1;让多数=nums[0];for(leti=1;i{//计算lo和hi之间的num个数letcount=0;for(leti=lo;i<=hi;i++){if(nums[i]===num)count++;}}返回计数；};constgetMode=(lo,hi)=>{if(lo===hi)returnnums[lo];//分成更小的间隔letmid=Math.floor((lo+hi)/2);让left=getMode(lo,mid);letright=getMode(mid+1,hi);如果（左===右）返回左；letleftCount=getCount(left,lo,hi);//统计区间内左边的个数letrightCount=getCount(right,lo,hi);//统计区间内右边的个数returnleftCount>rightCount?left:right;//返回最左和最右的一个};返回getMode(0,nums.length-1);};938。二叉搜索树的范围和（简单）给定两个Fork搜索树的根节点root，并返回值在范围[low,高的]。示例1：输入：root=[10,5,15,3,7,null,18]，low=7，high=15输出：32示例2：输入：root=[10,5,15,3,7,13,18,1,null,6],low=6,high=10output:23提示：树的节点数在[1,2*104]范围内1<=Node.val<=1051<=low<=high<=105所有Node.val都不同方法一：dfs复杂度：时间复杂度O(n)，空间复杂度O(n)js:varrangeSumBST=function(root,low,high){if(!root){返回0;}if(root.val>high){returnrangeSumBST(root.left,low,high);}if(root.valhigh){q.push(node.left);}elseif(node.val
