题解 | #二叉树中的最大路径和,dfs + 记忆化搜索 + hashMap,垃圾解法#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    
    int max = Integer.MIN_VALUE ;
    HashMap<TreeNode , Integer> map = new HashMap<>() ;
    HashMap<TreeNode , Integer> map2 = new HashMap<>() ;
    public int maxPathSum (TreeNode root) {
        if(root == null) return 0 ;
        pre(root) ;
        return max ;
    }
    //中序遍历
    public void pre(TreeNode root) {
        if(root == null) return ;
        int one = help(root) ;
        int two = map2.get(root) ;
        int res = max(one , two) ;
        max = max(res , max) ;
        pre(root.left) ;
        pre(root.right) ;
    }
    public int help(TreeNode root) {
        if(root == null) return -1001 ;
        Integer get = map.get(root) ;
        if(get != null) return get ;
        if(root.left == null && root.right == null) {
            map.put(root , root.val) ;
            map2.put(root , root.val) ;
            return root.val ;
        } 
        int l = help(root.left) ;
        int r = help(root.right) ;
        int res = max(l + root.val , r + root.val , root.val) ;
        map.put(root , res) ;
        map2.put(root , l + r + root.val) ;
        return res ;
        
    }
    public int max(int...args) {
        int max = Integer.MIN_VALUE ;
        for(int a : args) {
            if(a > max) {
                max = a ;
            }
        }
        return max ;
    }
}