脸家新鲜跪经

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

我觉得这题不难啊，和124一样的，你找到max path 的root 的时候set a pointer to it. tree node 稍微改一下， 每个tree node 要记录 max path to end 是 left or right， 然后你最后回到 你set 那个root 左右同时加 你记录的 path就可以了， 比124 多几行code

Cacacactus 发表于 2017-12-4 11:10

宝宝不哭，我给你写了一个返回路径的


    int helper(TreeNode* root, int& max_path, vector<int>& max_path_vec, vector<int>& path){
         if(!root) return 0;
                 vector<int> left_path, right_path;
         int left = max(helper(root->left, max_path, max_path_vec, left_path), 0);
         int right = max(helper(root->right, max_path, max_path_vec, right_path), 0);
             if(max_path < root->val + left + right){
                    max_path = root->val + left + right;
                    max_path_vec.clear();
                    max_path_vec.insert(max_path_vec.end(), left_path.rbegin(), left_path.rend());
                    max_path_vec.push_back(root->val);
                    max_path_vec.insert(max_path_vec.end(), right_path.begin(), right_path.end());
                 }
                 path.clear();
                 path.push_back(root->val);
                 if(left > right){
                    path.insert(path.end(), left_path.begin(), left_path.end());
                 }
                 else path.insert(path.end(), right_path.begin(), right_path.end());
         return root->val + max(left, right);
    }