@@ -0,0 +1,1334 @@
+// Given a binary tree, find the maximum path sum.%0A%0A// The path may start and end at any node in the tree.%0A%0A// For example:%0A// Given the below binary tree,%0A%0A//        1%0A//       / %5C%0A//      2   3%0A// Return 6.%0A%0A/**%0A * Definition for binary tree%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    public int maxPathSum(TreeNode root) %7B%0A        if(root == null) return 0;%0A        int%5B%5D res = new int%5B1%5D;%0A        res%5B0%5D = Integer.MIN_VALUE;%0A%0A        dfs(root, res);%0A%0A        return res%5B0%5D;%0A    %7D%0A%0A    public int dfs(TreeNode node, int%5B%5D res)%7B%0A    %09if(node == null) return 0;%0A%0A    %09int left = dfs(node.left, res) ;%0A    %09int right = dfs(node.right, res) ;%0A%0A    %09// currentMax candidates(open path not closed, path should be able to extend): %0A    %09//%091. node; 2. node + single child.%0A    %09int currentMax = Math.max(node.val, left %3E right? left + node.val : right + node.val);%0A%0A    %09// globalMax candidates:(both open&closed path should be considered):%0A    %09// 1.stored max; 2.node; 3.node + single child; 4.node + both children.%0A    %09int globalMax = Math.max(res%5B0%5D, Math.max(node.val, Math.max(left + node.val + right, left %3E right? node.val + left : node.val + right)));%0A%0A    %09res%5B0%5D = globalMax;%0A%0A    %09return currentMax;%0A    %7D%0A%7D

add binary tree maximum path sum solution