题解 | 二叉树中的最大路径和

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    // 定义最大路径和
    int res = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        DFS(root);
        return res;
    }

    // 定义深度优先搜索方法
    public int DFS(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 定义左边路径的最大深度和
        int Max_left = Math.max(0, DFS(root.left));
        // 定义右边路径的最大深度和
        int Max_right = Math.max(0, DFS(root.right));
        // 更新最大路径和
        res = Math.max(res, root.val + Max_left + Max_right);
        // 返回最大路径的和
        return Math.max(Max_left, Max_right) + root.val;
    }
}

采用DFS深度优先搜索的递归方法进行最大路径求和，一条道走到深处，无论走左边路径还是右边路径，最终都是为了得到最大路径和，分为两种情况：

1、走左边路径：在该路径中，从父节点走到最深处的叶子节点的路径值为DFS(root.left)，最大路径值需要加上当前节点的值。即DFS(root.left)+root.val。

2、走右边路径：在该路径中，从父节点走到最深处的叶子节点的路径值为DFS(root.right)，最大路径值需要加上当前节点的值。即DFS(root.right)+root.val。

递归结束后，需要求出左边最大路径和 与 右边最大路径和的最大值，用二者中的最大值加上当前节点值就是最大路径和。

即root.val+Math.max(DFS(root.left)+root.val, DFS(root.right)+root.val).