Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
1 2 3 4 5 6 7
Input: [1,2,3]
1 / \ 2 3
Output: 6
Example 2:
1 2 3 4 5 6 7 8 9
Input: [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7
Output: 42
分析
二叉树里路径可以从任意节点开始到任意节点结束,二叉树可以用 DFS 来遍历,先算出左右子树的结果 left, right, 如果大于0,则对结果有利,加上 left 或 right 后与之前的 max 进行比较,取较大值。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ classSolution{ int max = Integer.MIN_VALUE; publicintmaxPathSum(TreeNode root){ dfs(root); return max; } privateintdfs(TreeNode root){ if (root == null) { return0; } int left = Math.max(dfs(root.left), 0); int right = Math.max(dfs(root.right), 0); max = Math.max(max, root.val + left + right); return root.val + Math.max(left, right); } }