请实现一个算法：给定一棵二叉树，每个节点包含一个整数值，请找出二叉树中任意一条路径上所有节点值之和的最大值。路径可以从任意节点出发，到任意节点结束，路径中每个节点只能经过一次，且路径方向可以不经过根节点。
考察说明
考察二叉树遍历、递归/DP设计与全局最优解维护
回答思路
- 正确理解路径定义：可从任意节点出发和结束
- 设计递归后序遍历，返回以当前节点为起点的最大单边路径和
- 在递归中维护全局最大值，比较左右子树合并路径与单边路径
- 处理节点值为负数的边界情况
- 说明时间复杂度为 O(N)，空间复杂度为递归栈深度 O(H)
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。