- class Solution {
- public int maxPathSum(TreeNode root) {
- maxSum = Integer.MIN_VALUE;
- gainFromSubtree(root);
- return maxSum;
- }
- private int maxSum;
- // post order traversal of subtree rooted at `root`
- private int gainFromSubtree(TreeNode root) {
- if (root == null) {
- return 0;
- }
- // add the path sum from left subtree. Note that if the path
- // sum is negative, we can ignore it, or count it as 0.
- // This is the reason we use `Math.max` here.
- int gainFromLeft = Math.max(gainFromSubtree(root.left), 0);
- // add the path sum from right subtree. 0 if negative
- int gainFromRight = Math.max(gainFromSubtree(root.right), 0);
- // if left or right path sum are negative, they are counted
- // as 0, so this statement takes care of all four scenarios
- maxSum = Math.max(maxSum, gainFromLeft + gainFromRight + root.val);
- // return the max sum for a path starting at the root of subtree
- return Math.max(gainFromLeft + root.val, gainFromRight + root.val);
- }
- }
[text] tree
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
Editor
You can edit this paste and save as new: