算法康复训练18

1. 知识点总结

题目	难度	知识点
买股票的最佳时机	🐸	数组
二叉树中的最大路径和	🐸🐸🐸	树+递归需要回炉

2. 分题题解

2.1 买股票的最佳时机

这题不会可以隐身了🤪，过~

2.2 二叉树中的最大路径和

• 失败的简单中序遍历——错误原因是子节点回到根节点（路径不通的问题）

class Solution {
public:
    int ans=-INT_MAX;
    int preSum=0;
    bool flag=false;
    void inTravel(TreeNode *root){
        if(root==NULL){
            return;
        }else{
            inTravel(root->left);
            //操作：
            cout<<"当前结点："<<root->val<<" \n";
            if(root->val<0){
                ans=max(ans,root->val);
                if(flag){
                    ans=max(ans,preSum);
                }
                preSum=0;
            }else{
                flag=true;
                preSum+=root->val;
            }
            inTravel(root->right);
        }
    }
    int maxPathSum(TreeNode* root) {
        //最大路径和
        inTravel(root);
        if(flag){
            
            ans=max(preSum,ans);
        }
        return ans;
    }
};

• 看了题解才知道如何正确递归，话说回来注意结点在路径中只能走一次这个条件在递归中的使用

class Solution {
public:
    int ans=-INT_MAX;
    int getMax(TreeNode*root){
        if(root==NULL){
            return 0;
        }else{
            int left=max(getMax(root->left),0);
            int right=max(getMax(root->right),0);
            int sum=right+left+root->val;
            ans=max(ans,sum);
            //限制每个结点只能走一次
            return root->val+max(right,left);
        }
    }
    int maxPathSum(TreeNode* root) {
        //最大路径和
        getMax(root);
        return ans;
    }
};

3. 参考资料

碎碎念：

操作系统结束后准备给自己放两天半的假期，然后所谓的假期就是做模式识别的大作业、写图像作业、完成形势与政策考试以及团委一些零零碎碎的事情（今天说是要换届了，开森！）

模式识别的作业我选的方向做的是一个人脸表情识别系统（(｡･∀･)ﾉﾞ嗨为啥不能做NLP捏，那样俺就不用从头再写一遍了哇），基于CNN和torch，很有意思的项目，遗憾的是训练跑的次数不多，cpu跑的（本来在 蹭实验室的GPU但是后来好像内存不够被卡了？想着学长学姐优先级高所以就转回本地啦），精度最后控制到了72%，属于正常水平！