Contents
  1. 1. Problem Description
  2. 2. Solution
  3. 3. 解题思路

Problem Description

Given a 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.

For example:
Given the below binary tree,

1
2
3
1
/ \
2 3

Return 6.

problem link:
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
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;
}
}

解题思路

每一个结点可以选和不选,处理方法就是:int left = Math.max(0, maxPathDown(node.left));,其中的 Math.max(0, x),当取值为 0 时就是不取这个结点。

全局变量 maxValue 就覆盖了子树中的 ^ 这种类型,例如子树如下:

1
2
3
x
a y
b c

则 b->a->c 这种路径的最大值被 maxValue 保存了。而 b->a->x->y 这种经过根节点的路径被 Math.max(left, right) + node.val; 覆盖了。

Contents
  1. 1. Problem Description
  2. 2. Solution
  3. 3. 解题思路