class Solution {
public:
int max_ans = INT_MIN;
if (!root) {
return 0;
}
int left_ans = maxPathSum(root->left);
int right_ans = maxPathSum(root->right);
max_ans = max(max_ans,root->val);
max_ans = max(max_ans,left_ans+root->val);
max_ans = max(max_ans,right_ans+root->val);
max_ans = max(max_ans,root->val + left_ans + right_ans );
return max(root->val,max(left_ans + root->val, right_ans + root->val));
}
solve(root);
return max_ans;
}
};
Y2xhc3MgU29sdXRpb24gewpwdWJsaWM6CmludCBtYXhfYW5zID0gSU5UX01JTjsKaW50IHNvbHZlKFRyZWVOb2RlICpyb290KXsKICAgIAogICAgaWYgKCFyb290KSB7CgkJcmV0dXJuIDA7Cgl9CglpbnQgbGVmdF9hbnMgPSBtYXhQYXRoU3VtKHJvb3QtPmxlZnQpOwoJaW50IHJpZ2h0X2FucyA9IG1heFBhdGhTdW0ocm9vdC0+cmlnaHQpOwogICAgbWF4X2FucyA9IG1heChtYXhfYW5zLHJvb3QtPnZhbCk7CiAgICBtYXhfYW5zID0gbWF4KG1heF9hbnMsbGVmdF9hbnMrcm9vdC0+dmFsKTsKICAgIG1heF9hbnMgPSBtYXgobWF4X2FucyxyaWdodF9hbnMrcm9vdC0+dmFsKTsKCW1heF9hbnMgPSBtYXgobWF4X2Fucyxyb290LT52YWwgKyBsZWZ0X2FucyArIHJpZ2h0X2FucyApOwoJcmV0dXJuIG1heChyb290LT52YWwsbWF4KGxlZnRfYW5zICsgcm9vdC0+dmFsLCByaWdodF9hbnMgKyByb290LT52YWwpKTsKICAgIAp9CmludCBtYXhQYXRoU3VtKFRyZWVOb2RlKiByb290KSB7Cglzb2x2ZShyb290KTsKICAgIHJldHVybiBtYXhfYW5zOwp9Cn07