【Leetcode】124. 二叉树中的最大路径和

题目给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1:输入: [1,2,3] 1 / \ 2 3输出: 6示例 2:输入: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7输出: 42题解这道题虽然是标记成hard难度的题目,但是我觉得主要是因为需要处理的细节可能需要仔细考虑,倒不是因为题目本身比较复杂。我们很容易想到用递归去解这道题。递归子问题：左子树的路径和 + 右子树的路径和 + 当前结点的数字class Solution { private int maxSum; public int maxPathSum(TreeNode root) { maxSum = Integer.MIN_VALUE; helper(root); return maxSum; } private int helper(TreeNode root) { if (root == null) return 0; int leftSum = Math.max(helper(root.left), 0); // 和0比较，要么要这个分支,要么不要这个分支 int rightSum = Math.max(helper(root.right), 0); // 当前节点路径下最大值和全局最大值做比较 maxSum = Math.max(leftSum + rightSum + root.val, maxSum); // 返回的是左右子树中最大的 + 当前结点的值作为这棵树的路径。因为必须要走根节点。 return Math.max(leftSum, rightSum) + root.val; }}考虑以下极端情况: -2 / \ -1 -3手撕代码QQ群：805423079， 群密码：1024