1 /**
 2      * Given a binary tree, find the maximum path sum.
 3      * The path may start and end at any node in the tree.
 4      * there are negative numbers
 5      * {9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
 6      * @param root
 7      * @return
 8      */
 9     public int maxPathSum(TreeNode root){
10         if(root == null)
11             return 0;
12         return subProblem(root);
13     }
14     /**
15      * 
16      * @param root
17      * @return
18      */
19     private int subProblem(TreeNode root){
20         
21         if(root == null)
22             return Integer.MIN_VALUE;
23         if(root.left == null && root.right == null)
24             return root.val;
25         //左子树的最大路劲和
26         int left = subProblem(root.left);
27         //右子树的最大路径和
28         int right = subProblem(root.right);
29         //经过root节点的最大路径和
30         int lc = maxSinglePath2(root.left);
31         int rc = maxSinglePath2(root.right);
32         int mid = lc>0?lc:0;
33         mid = rc>0? mid+rc:mid;
34         
35         return Math.max(left, right)>mid+root.val?Math.max(left, right):mid+root.val;
36     }
37     /**
38     /**
39      * 这种递归求从某个节点到叶节点路径上和最大的方法，容易出现TLE
40      * 因为这个方法要被subProblem反复使用
41      * 
42     private int maxSinglePath(TreeNode root){
43         if(root==null)
44             return 0;
45         if(root.left==null && root.right ==null)
46             return root.val;
47         int lc = maxSinglePath(root.left);
48         int lr = maxSinglePath(root.right);
49         return Math.max(lc, lr)+root.val;
50     }*/
51     //通过另外开辟一个全局变量，存储从底层开始到每个节点（key）的路径的最大和
52     //这样可以避免出现已经计算过的节点被反复计算
53     HashMap<TreeNode,Integer> ns = new HashMap<TreeNode,Integer>();
54     private int maxSinglePath2(TreeNode root){
55         if(root==null)
56             return 0;
57         if(root.left==null && root.right ==null)
58         {
59             ns.put(root, root.val);
60             return root.val;
61         }
62         int lc,rc;//到左、右节点的最大路径和
63         if(root.left!=null && ns.containsKey(root.left))
64             lc = ns.get(root.left);
65         else
66             lc = maxSinglePath2(root.left);
67         if(root.right!=null && ns.containsKey(root.right))
68             rc = ns.get(root.right);
69         else
70             rc = maxSinglePath2(root.right);
71         //this is very important!!!!!! 因为节点的值可能为负数，如果到左右两节点的最大路径和是负数的话，我就直接从当前节点作为当前节点的路径最大和的起始点
72         if(Math.max(lc, rc)>0)
73             ns.put(root, Math.max(lc, rc)+root.val);
74         else
75             ns.put(root, root.val);
76         return ns.get(root);
77         //return Math.max(lc, rc)+root.val;
78     }