给定一棵二叉树，每个节点包含一个整数值，请计算并返回该树的最大路径和。路径被定义为从任意节点出发，沿父子连接向下到达任意节点的一条路径，路径至少包含一个节点，且不一定经过根节点。
考察说明
考察对二叉树遍历和动态规划思想的理解，以及处理负值节点的边界能力
回答思路
- 正确理解路径定义，即任意节点到其某个后代节点的路径
- 能识别后序遍历是计算每个节点贡献值的关键
- 正确处理节点值为负的情况，允许路径在任意节点开始和结束
- 考虑跨左右子树的路径，通过比较全局最大值
- 正确实现递归函数返回单边最大贡献值
- 代码能处理空树或单节点边界情况
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。