自底向上的递归。
对于二叉树,我们令每个结点作为 LCALCALCA (最近公共祖先),
结点 uuu 作为 LCALCALCA , 经过它的最大路径 === 往左子树的最大路径 +++ 往右子树的最大路径 +++ 它自己的路径 。
有 ans=max(ans,vu+l+rans = max(ans,v_u+l+rans=max(ans,vu+l+r)
对于结点 uuu 的上层结点,经过 uuu 的最大路径 =max(=max(=max( 往左走 ,,, 往右走 )+)+)+ 它自己的路径
有 pathu=max(l,r)+vupath_u=max(l,r)+v_upathu=max(l,r)+vu
递归时,自底向上,记录结点的左右最大路径 l/rl/rl/r ,维护结点作为 LCALCALCA 的 ansansans 。遇到空结点,没有路径,即为 000 。
class Solution {
public:int ans;int maxPathSum(TreeNode* root) {ans = INT_MIN;dfs(root);return ans;}int dfs(TreeNode *root){if(!root) return 0;int l = max(0,dfs(root->left)),r = max(0,dfs(root->right));ans = max(ans,l+r+root->val);return root->val + max(l,r);}
};