二叉树中的最大路径和

发表于 | 分类于 | 阅读次数：
本文字数： 1.2k | 阅读时长 ≈ 3 分钟

问题提出

#124 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 :

1
2
3
4
5
6
7
8
9
10
> 输入: [-10,9,20,null,null,15,7]
> 
>    -10
>    / \
>   9  20
>     /  \
>    15   7
> 
> 输出: 42
>

解法

考虑下面这棵二叉树：

1
2
3
4
5
    a
   /  \
  b    c
 / \  / \
d  e  f  g

如果最长路径包括根节点a，则最长路径为max{a, a + b', a + c', a + b' + c'}，这里的b'指的并不是b这个节点的值，而是以b为根节点的子树的最长路径值（路径的一个端点是b），即

1
b' = max{b, b + d', b + e'}

下面考虑最长路径不包括根节点a的情况，那么最长路径要么在子树b中，要么在子树c中，此时再将b和c看作根节点，重复上述步骤，递归即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    calculateMaxSum(root, maxSum);
    return maxSum;
}

int calculateMaxSum(TreeNode *node, int &ms) {
    if (node == NULL) return 0;
    int localMaxSum = node->val;
    int nodeValue = node->val;
    int lvalue = calculateMaxSum(node->left, ms);
    int rvalue = calculateMaxSum(node->right, ms);

    if (lvalue > 0) localMaxSum += lvalue;
    if (rvalue > 0) localMaxSum += rvalue;
    if (localMaxSum > ms) ms = localMaxSum;

    if (lvalue > 0 || rvalue > 0) 
        nodeValue += (lvalue > rvalue) ? lvalue : rvalue;
    return nodeValue;
}