image.png
要点：
- 最大路径和可能出现在三种情况中：
左子树
右子树
根节点与左右子树 - 返回值，返回当前节点和左右分支中的一支的最大值
- 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的分支 + 节点最大值
}
int maxPathSum(TreeNode* root) {
int maxsum = INT_MIN;
dfs(root, maxsum);
return maxsum;
}
网友评论