请实现一个算法：求二叉树中的最大路径和，并说明路径的定义和复杂度。

Question

Accepted Answer

考察点：考察二叉树遍历、分治思想和算法设计能力。回答思路：明确路径定义（从任意节点出发到任意节点，路径至少包含一个节点，且每个节点最多出现一次） 使用后序遍历自底向上计算每个节点的贡献值 正确处理递归返回值与全局最大值的更新逻辑 能给出时间复杂度O(n)和空间复杂度O(h)的说明

考察说明