知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 31 - 二叉树中的最大路径和 ## 题目(LeetCode 124) 路径可以从任意节点到任意节点,求最大路径和。 ## 解法:后序遍历 ```java class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } private int dfs(TreeNode node) { if (node == null) return 0; int left = Math.max(0, dfs(node.left)); // 负数就不要 int right = Math.max(0, dfs(node.right)); maxSum = Math.max(maxSum, node.val + left + right); // 经过当前节点的路径 return node.val + Math.max(left, right); // 向上只能选一边 } } ``` ## 复杂度 - 时间 O(n),空间 O(n) ## 一句话总结 每个节点算"经过自己的最大路径和"更新全局,向上返回时只能选一边。 ## 说明 二叉树最大路径和问题的核心约束是:路径经过某节点时,只能选择左或右子树中的一条(不能同时向两边延伸后再向上)。这个约束决定了**后序遍历 + 全局变量**是唯一自然的解法框架。 没有更优的替代方案,当前解法已是 O(n) 时间 O(n) 空间的最优解。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入