package leetcode;

/**
 * https://leetcode.com/problems/binary-tree-maximum-path-sum/
 */
public class Problem124 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public int maxPathSum(TreeNode root) {
        return 0;
    }

    public static void main(String[] args) {
        Problem124 prob = new Problem124();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(prob.maxPathSum(root)); // 6

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
        System.out.println(prob.maxPathSum(root)); // 17

        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(10);
        root.left.right = new TreeNode(10);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(1);
        System.out.println(prob.maxPathSum(root)); // 22
    }
}

@@ -270,150 +270,117 @@
   %7D%0A
-%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D%0A    %7D%0A%0A    public int maxPathSum(TreeNode root) %7B
+    %7D%0A%0A    public int maxPathSum(TreeNode root) %7B%0A        Max max = new Max();%0A        maxPathSum(root, max);
 %0A   
@@ -391,17 +391,25 @@
  return 
-0
+max.value
 ;%0A    %7D%0A
@@ -414,29 +414,30 @@
 %7D%0A%0A    p
-ublic
+rivate
  static 
 void mai
@@ -432,884 +432,530 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem124 prob = new Problem124();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(2)
+class Max %7B%0A        private int value = Integer.MIN_VALUE
 ;%0A    
+%7D%0A%0A
     
-root.right = new TreeNode(3);%0A        System.out.println(prob.maxPathSum(root)); // 6%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(4);%0A        root.left.right = new TreeNode(5);%0A        root.right = new TreeNode(3);%0A        root.right.right = new TreeNode(6);%0A        System.out.println(prob.maxPathSum(root)); // 17%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(10);%0A        root.left.right = new TreeNode(10);%0A        root.right = new TreeNode(1);%0A        root.right.left = new TreeNode(1);%0A        root.right.right = new TreeNode(1);%0A        System.out.println(prob.maxPathSum(root)); // 22
+private static int maxPathSum(TreeNode node, Max max) %7B%0A        if (node == null) %7B%0A            return 0;%0A        %7D%0A        int a = maxPathSum(node.left, max);%0A        int b = maxPathSum(node.right, max);%0A        if (a + node.val %3C node.val) %7B%0A            a = 0;%0A        %7D%0A        if (b + node.val %3C node.val) %7B%0A            b = 0;%0A        %7D%0A        max.value = Math.max(max.value, a + b + node.val);%0A        return Math.max(node.val + a, node.val + b);
 %0A   

Solve problem 124