[text] tree

Viewer

  1.  
  2. class Solution {
  3.     public int maxPathSum(TreeNode root) {
  4.         maxSum = Integer.MIN_VALUE;
  5.         gainFromSubtree(root);
  6.         return maxSum;
  7.     }
  8.  
  9.     private int maxSum;
  10.  
  11.     // post order traversal of subtree rooted at `root`
  12.     private int gainFromSubtree(TreeNode root) {
  13.         if (root == null) {
  14.             return 0;
  15.         }
  16.  
  17.         // add the path sum from left subtree. Note that if the path
  18.         // sum is negative, we can ignore it, or count it as 0.
  19.         // This is the reason we use `Math.max` here.
  20.         int gainFromLeft = Math.max(gainFromSubtree(root.left), 0);
  21.  
  22.         // add the path sum from right subtree. 0 if negative
  23.         int gainFromRight = Math.max(gainFromSubtree(root.right), 0);
  24.  
  25.         // if left or right path sum are negative, they are counted
  26.         // as 0, so this statement takes care of all four scenarios
  27.         maxSum = Math.max(maxSum, gainFromLeft + gainFromRight + root.val);
  28.  
  29.         // return the max sum for a path starting at the root of subtree
  30.         return Math.max(gainFromLeft + root.val, gainFromRight + root.val);
  31.     }
  32. }
  33.  
  34.  

Editor

You can edit this paste and save as new:


File Description
  • tree
  • Paste Code
  • 26 Nov-2022
  • 1.12 Kb
You can Share it: