fork download
copy 
  1. package trees.leetcode;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. public class MaximumSumPath {
  7.  
  8.     public static class TreeNode {
  9.         int val;
  10.         TreeNode left;
  11.         TreeNode right;
  12.  
  13.         TreeNode(int x) {
  14.             val = x;
  15.         }
  16.     }
  17.     static List<Integer> path;
  18.     static int sum = 0;
  19.     public List<Integer> maxPathSum(TreeNode root) {
  20.         if ( root == null)
  21.             return new ArrayList<>();
  22.  
  23.         sum = Integer.MIN_VALUE;
  24.  
  25.         maxPathSumUtil(root);
  26.         return path;
  27.  
  28.     }
  29.  
  30.     private List<Integer> maxPathSumUtil(TreeNode root)   {
  31.         if ( root == null)
  32.             return new ArrayList<>();
  33.  
  34.         List<Integer> currRoot = new ArrayList<>();
  35.         List<Integer> leftTree = maxPathSumUtil(root.left);
  36.  
  37.         int leftTreeSum = Math.max(0, leftTree.stream().mapToInt(l -> l).sum());
  38.         int currSum = leftTreeSum;
  39.         if ( leftTreeSum > 0)
  40.             currRoot.addAll(leftTree);
  41.  
  42.         currSum += root.val;
  43.         currRoot.add(root.val);
  44.  
  45.         List<Integer> rightTree = maxPathSumUtil(root.right);
  46.         int rightTreeSum = Math.max(0, rightTree.stream().mapToInt( l -> l ).sum());
  47.         currSum += rightTreeSum;
  48.         if ( rightTreeSum > 0)
  49.             currRoot.addAll(rightTree);
  50.  
  51.         if ( currSum > sum) {
  52.             path = new ArrayList<>();
  53.             path.addAll(currRoot);
  54.             sum = currSum;
  55.         }
  56.  
  57.         if ( leftTreeSum > rightTreeSum)    {
  58.             currRoot.removeAll(rightTree);
  59.         }
  60.         else if ( rightTreeSum > leftTreeSum)   {
  61.             currRoot.removeAll(leftTree);
  62.         }
  63.  
  64.         return currRoot;
  65.     }
  66.  
  67.     public static void main(String args[])  {
  68.         TreeNode root = new TreeNode(-1);
  69.         root.left = new TreeNode(-2);
  70.         root.left.left = new TreeNode(3);
  71.         root.left.left.left = new TreeNode(100);
  72.         root.left.left.right = new TreeNode(101);
  73.         root.right = new TreeNode(3);
  74.         root.right.left = new TreeNode(4);
  75.         root.right.right = new TreeNode(7);
  76.  
  77.         new MaximumSumPath().maxPathSum(root).forEach( t -> System.out.print( t  + " "));
  78.     }
  79.  
  80. }
  81.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:6: error: class MaximumSumPath is public, should be declared in a file named MaximumSumPath.java
public class MaximumSumPath {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/r9u6qD
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!