二叉树中的最大路径和

LeetCode每日一题，124.Binary Tree Maximum Path Sum

先看题目描述

算法和思路

这道题是典型的子树递归，用 max 来维护全局最大路径和，每当递归到一个节点时，用 left 来表示递归求得的左边分支最大路径和，right 表示递归求得的右边分支最大路径和，root.val + left + right 与 max 进行比较来维护 max，然后返回经过 root 的单边分支最大值给上游，递归结束后返回 max 即为全局最大路径和

算法源码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        dfs(root);
        return max;

    }

    public int dfs(TreeNode root) {
        int left = 0;
        int right = 0;
        if (root.left != null) left = Math.max(dfs(root.left), 0);
        if (root.right != null) right = Math.max(dfs(root.right), 0);
        max = Math.max(max, left + right + root.val);
        return root.val + Math.max(left, right);
    }
}