@@ -0,0 +1,1684 @@
+/**%0A * Problem Link: https://leetcode.com/problems/binary-tree-maximum-path-sum/%0A * %0A * Definition for a binary tree node.%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0Apublic class Solution %7B%0A    private HashMap%3CTreeNode, Integer%3E map;%0A    private int maxSum;%0A    public int maxPathSum(TreeNode root) %7B%0A        map = new HashMap%3CTreeNode, Integer%3E();%0A        maxSum = Integer.MIN_VALUE;%0A        pathSum(root);%0A        return maxSum;%0A    %7D%0A    %0A    private void pathSum(TreeNode root) %7B%0A        if(root == null) return;%0A        pathSum(root.left);%0A        pathSum(root.right);%0A        %0A        map.put(root, root.val);%0A        // Just root itself;%0A        if(root.left == null && root.right == null) %7B%0A            map.put(root, root.val);%0A        %7D %0A        // root itself or with left branch.%0A        else if(root.left != null && root.right == null) %7B%0A            int left = map.get(root.left);%0A            if(left %3E 0) map.put(root, left + root.val);%0A        %7D%0A        // root itself or with right branch.%0A        else if(root.left == null && root.right != null) %7B%0A            int right = map.get(root.right);%0A            if(right %3E 0) map.put(root, right + root.val);%0A        %7D%0A        // root itsel, with left branch only, with right branch only, with both branches.%0A        else %7B%0A            int left = map.get(root.left);%0A            int right = map.get(root.right);%0A            if(Math.max(left, right) %3E 0) map.put(root, Math.max(left, right) + root.val);%0A            maxSum = Math.max(maxSum, left + right + root.val);%0A        %7D%0A        maxSum = Math.max(maxSum, map.get(root));%0A    %7D%0A%7D%0A

Create Binary_Tree_Maximum_Path_Sum.java