二叉树中的最大路径和

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)。