题目

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

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

示例 1:

1
2
3
4
5
6
7

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

1
2
3
4
5
6
7
8
9

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

题解

这道题倒是简单，很容易就想出来了。对于树的结构来说，无非是左子树、根结点、右子树，那么路径实际上就有下面这几种：

  1. 根节点
  2. 左子树+根节点
  3. 右子树+根节点
  4. 左子树+根节点+右子树

我们遍历整个树，求上面4种情况的最大值即可。我最开始的实现如下，稍微有点复杂。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

int maxPath(TreeNode* root, int &max_value) {
   if (root == nullptr) return INT_MIN;

   int left_value = INT_MIN;
   int right_value = INT_MIN;

   left_value = maxPath(root->left, max_value);
   int root_value = root->val;    
   right_value = maxPath(root->right, max_value);

   int left_root_right = root_value;
   int right_root = root_value;
   int left_root = root_value;
   
   // 为了避免负数相加导致溢出，这里进行判断
   if (left_value != INT_MIN && right_value != INT_MIN)
       left_root_right += left_value + right_value;

   // 同样为了避免溢出，这里进行判断
   if (left_value != INT_MIN)
       left_root += left_value;
   if (right_value != INT_MIN)
       right_root += right_value;

   // 记录4种情况中的最大值
   max_value = max(max_value, root_value);
   max_value = max(max_value, left_root);
   max_value = max(max_value, right_root);
   max_value = max(max_value, left_root_right);

   // 返回当前树情况下的最大值
   return max(left_root, max(root_value, right_root));
}

int maxPathSum(TreeNode* root) {
   int max_value = INT_MIN;
   maxPath(root, max_value);
   return max_value;
}

这里的实现有些蛋疼，因为将初始值设为了INT_MIN，而当两个INT_MIN相加时将会导致溢出，导致计算错误，所以这里进行了判断处理。

maxPath函数的第二个参数用来记录整个遍历过程中的最大值，而maxPath函数本身会返回当前子树路径的最大值，这个最大值中是一定要包含根结点的，否则将无法形成路径。

在参考了讨论之后，发现我自己的实现比较复杂，主要还是考虑了负数的计算，但实际上负数并不对最大值有效，因此我们可以将它给排除掉。但考虑所有数都为负数的情况，这种情况下某个结点肯定为最大值，因此我们在计算最大值时，是不能将根结点给排除掉的。

参考讨论的实现如下，思路基本相同：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int maxPath(TreeNode* root, int &max_value){
    if (root == nullptr) return 0;
    int left = maxPath(root->left, max_value);
    int right = maxPath(root->right, max_value);

    // 这里使用max排除掉负数
    int left_root_right = root->val + max(0, left) + max(0, right);
    int ret = root->val + max(0, max(left, right));
    max_value = max(max_value, max(left_root_right, ret));
    return ret;
}

int maxPathSum(TreeNode* root) {
    int max_value = INT_MIN;
    maxPath(root, max_value);
    return max_value;
}