请实现一个函数，计算二叉树中任意节点路径的最大路径和，并说明算法的复杂度。
考察说明
考察二叉树遍历、递归分解与后序遍历求解最大路径和的能力
回答思路
- 准确理解路径定义：从任意节点出发，沿父/子连接到达另一节点的路径，每条路径至少包含一个节点
- 使用后序遍历递归，以当前节点为路径的最高点，计算其左子树和右子树贡献的最大单边路径和
- 正确处理负值贡献：若子树贡献为负则取0，避免引入负收益
- 维护全局最大路径和，并比较包含当前节点时的路径和与历史最大值
- 正确推导时间复杂度O(n)和空间复杂度O(h)，h为树高
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。