LeetCode 124.二叉树中的最大路径和

Posted on | In

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

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

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

示例 1: 

1
2
3
4
5
6
7
8
> 输入: [1,2,3]
> 
>        1
>       / \
>      2   3
> 
> 输出: 6
>

示例 2: 

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

思路： 首先要理解path的意思，本题path以我的理解是一条不分叉的线段。
不分叉可以出现以下情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 第一种：
    a
   / \			
  b   c
 
 第二种：
    a
   /
(左子树)

第三种：
    a
     \
     (右子树)

我所说的分叉的情况 如下图，d就是个分叉点：

1
2
3
4
5
    a
   /
  b
 /\
d  f

所以出现最大路径的值有三种情况：

  1. 当前节点加其左右子树（左右子树是单边分支）
  2. 当前节点加左子树加其祖父节点（左右子树是单边分支）
  3. 当前节点加右子树加其祖父节点（左右子树是单边分支）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if (!root)  return 0;
        int ans = INT_MIN;
        helper(root, ans);
        return ans;
    }
    int helper(TreeNode* root, int& sum){
        if (!root)  return 0;
        int left = helper(root->left, sum);		// 左
        int right = helper(root->right, sum);	// 右
        int lmr = root->val + max(0, left) + max(0, right);// l m r 情景1
        int ret = root->val +max(0, max(left, right));	//单分支
        sum = max(sum, max(ret, lmr));			// 更新最大值
        return ret;								// 返回最大的单边
    }
};