力扣热门100题之二叉树中的最大路径和

核心思路一句话对每个节点计算它能向上提供的最大贡献自身值 max(左贡献, 右贡献)以当前节点为转折点的路径和自身值 左贡献 右贡献全局维护一个最大值不断更新完整代码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ 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; // 左、右贡献如果是负数就不取0 int left Math.max(dfs(node.left), 0); int right Math.max(dfs(node.right), 0); // 当前节点作为转折点的路径和用来更新全局最大 int curPath node.val left right; maxSum Math.max(maxSum, curPath); // 返回给父节点只能选一条路 (只能选做或者右中较大的一边然后才能继续向上拼接新值) return node.val Math.max(left, right); } }