- 我们使用递归方法遍历树的每个节点。
- 对于每个节点,我们计算: a) 包含该节点和左子树的最大路径和 b) 包含该节点和右子树的最大路径和 c) 包含该节点及其左右子树的路径和
- 我们持续更新全局最大路径和(maxSum)。
- 函数返回当前节点能够贡献的最大值(节点值加上左子树或右子树中的较大者)。
- 这种方法的时间复杂度是O(N),其中N是树中的节点数,因为我们需要访问每个节点一次。空间复杂度在最坏情况下(树完全不平衡)是O(N),在最好情况下(树完全平衡)是O(log N),这是由于递归调用栈的开销