124. Binary Tree Maximum Path Sum

Leetcode Tree Depth-first Search

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

分析

这道题目不太容易想到好的解决方法。一种思路是依次求出某节点左子树和右子树的最大路径和，那么以该节点作为根节点的树的最大路径和等于左子树和右子树的最大路径和加上根节点的值。递归求解某颗子树的最大路径和：

• 一个路径从起点到终点，可以往上走几步，然后再往下走几步。但是一旦往下走，它不能再往上走。每个路径有一个最高的节点，也是该路径上的最近共同祖先(LCA, 参考LeetCode 235. Lowest Common Ancestor of a Binary Search Tree)。
• 一个递归方法maxPathDown(TreeNode node):
  1. 计算最高节点即node的最大路径和，如果需要更新最大值maxValue；
  2. 返回可延伸到输入节点(node)的父节点的最大路径和。

private int maxValue;
public int maxPathSum(TreeNode root) {
    maxValue = Integer.MIN_VALUE;
    maxPathDown(root);
    return maxValue;
}

private int maxPathDown(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, maxPathDown(node.left));
    int right = Math.max(0, maxPathDown(node.right));
    maxValue = Math.max(maxValue, left + right + node.val);
    return Math.max(left, right) + node.val;
}