二叉树中的最大路径和
Binary Tree Maximum Path Sum
题目详情
问题：二叉树中的最大路径和
考察：动态规划、树、深度优先搜索
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/binary-tree-maximum-path-sum
英文原题
Problem: Binary Tree Maximum Path Sum
Patterns: Dynamic Programming, Tree, Depth-First Search
Recency: 6mo
Link: https://leetcode.com/problems/binary-tree-maximum-path-sum
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：后序遍历每个节点，计算从该节点向父节点延伸的最大单边贡献；负贡献直接舍弃为 0。用左贡献 + 当前值 + 右贡献更新全局最大路径和。
复杂度：每个节点访问一次，时间 O(n)，递归栈 O(h)。
英文解析
Approach: Use postorder DFS. For each node, return the best one-sided contribution that can be extended to its parent, discard negative child contributions, and update a global answer with `left + node.val + right`.
Complexity: Time , recursion stack .