image.png
要點：
- 最大路徑和可能出現(xiàn)在三種情況中：
左子樹
右子樹
根節(jié)點與左右子樹 - 返回值，返回當前節(jié)點和左右分支中的一支的最大值
- maxsum 存放的事
int dfs(TreeNode* root, int& maxsum){
if(!root) return 0;
int l = dfs(root->left, maxsum); // l: left child的分支最大值,
int r = dfs(root->right, maxsum); //r: right child 的分支最大值
maxsum = max(l+r+root->val, maxsum); // 和當前最大值比較
return root->val + max(l,r); //child的分支 + 節(jié)點最大值
}
int maxPathSum(TreeNode* root) {
int maxsum = INT_MIN;
dfs(root, maxsum);
return maxsum;
}
