2024.7.19

**每日一题**

3096.得到更多分数的最少关卡数目，这道题是一个考察前缀和的题目，根据题意我们需要先把数组的0转为-1，然后计算两个部分的数组和，所以我们可以现预处理出前缀和数组，然后枚举每个点作为切分点，除了最后一个点，然后判断是否符合条件，否则输出-1.

class Solution { public:     int minimumLevels(vector& possible) {         int n = possible.size();         for(int i =0;i sum(n,0);         sum[0]=possible[0];         for(int i =1;isum[n-1]-sum[i])){                 return i+1;             }         }         return -1;     } };

124.二叉树中的最大路径和，这是一道考察递归的题目，从根节点出发，类似于dfs，分别递归寻找左右节点的路径和，直到叶子节点再返回，从叶子节点往上更新以每个节点为根节点的最大路径，直到返回根节点，用一个变量来维护答案.

class Solution { public:     int ans = -10000000;     int getSum(TreeNode* root){         if(root==nullptr) return 0;         int leftSum = max(getSum(root->left),0);         int rightSum = max(getSum(root->right),0);         int cnt = root->val+leftSum+rightSum;         ans = max(ans,cnt);         return root->val+max(leftSum,rightSum);     }      int maxPathSum(TreeNode* root) {          int a = getSum(root);          return ans;     } };

543.二叉树的直径，这道题是一道考察递归的题目，按照树的一般算法，维护一个最大直径答案值，定义一个递归函数，开头是递归返回条件，即当前节点为空节点就返回0，否则分别往左和往右递归，维护每个节点的最大深度为左右最大深度中的最大值再加一，答案用左右节点的最大深度的和再加一来维护.

class Solution { public:     int ans;     int depth(TreeNode* root){         if(root==nullptr) return 0;         int L=depth(root->left);         int R=depth(root->right);         ans=max(ans,L+R+1);         return max(L,R)+1;     }     int diameterOfBinaryTree(TreeNode* root) {         ans = 1;         depth(root);         return ans-1;         } };