二叉树最大路径和 - 可视化

寻找二叉树中节点值之和最大的路径

二叉树
当前节点
-
左贡献
-
右贡献
-
当前路径和
-
最大路径和
-
执行日志

算法核心思路

1. 递归遍历:从叶子节点向上计算每个节点的最大贡献值

2. 单边贡献:节点能向上贡献的最大路径和 = 节点值 + max(左贡献, 右贡献)

3. 完整路径:经过当前节点的完整路径 = 节点值 + 左贡献 + 右贡献

4. 更新全局最大值:比较完整路径和与全局最大值,取更大的

5. 负数贡献处理:如果某子树的贡献为负,视为0(不选那条边)

时间复杂度:O(n),空间复杂度:O(h),h 为树高