Binary Tree Maximum Path Sum
- 这题是diameter/height的扩展题. 因为题目还包含了不经过root的情况. 其实都是dfs recursion. 只是要同时保存single path和sum. 即
- single path是经过当前node的一边的max: Math.max(l.path, r.path)+root.v -> 经过当前node的边的最大值. 0->即经过此node的边为负.
- sum则是左右sum的最大值, 或者左右边最大值加上当前node.
由嘻唰唰blog题解里面分析的: 对于每一个node的Maximum Path Sum分2类:
- single path是指由该node出发向leaf的第一类path中最大的path sum
- 以x为LCA的第二类path中的最大path sum
Read full article from Leetcode freq 2 | 百变千幻衡山云雾十三式
No comments:
Post a Comment