Karl's Nest
0%

leetcode-day-29

Posted on In
Day-29 Binary Tree Maximum Path Sum

LeetCode 30 days Challenge - Day 29

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Binary Tree Maximum Path Sum

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:

1
2
3
4
5
6
7
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Solution

题目要求分析：给定一棵非空二叉树，求其中最大路径和。注意此处的路径不一定经过根结点，路径至少有一个节点。

解法：

本题需要注意的是，存在负数结点值，传统的递归思想无法满足题目要求。

对于当前结点，维护一个最大值变量res，我们需要考虑：

  1. 路径不允许分叉，那么若当前结点存在父节点、经过当前结点、还要向父节点走的路径只可能经过当前结点的左右子树之一，该定义是递归的。在下文，称这种情况为无分叉子树

  2. 最终经过当前结点的最大路径只有四种情况：

    1. 经过当前结点、不经过子树：无分叉子树最大路径和都为负数

      res = max(res, node->val + max(0, l) + max(0, r));

    2. 经过当前结点、当前节点的左子树、当前节点的右子树：两颗无分叉子树最大路径和都不为负数

      res = max(res, node->val + max(0, l) + max(0, r));

    3. 经过当前结点、当前节点的左子树：右无分叉子树最大路径和不为负数

      更新无分叉子树的最大路径和：node->val += max(0, max(l, r));

    4. 经过当前结点、当前节点的右子树：左无分叉子树最大路径和不为负数

      更新无分叉子树的最大路径和：node->val += max(0, max(l, r));

按以上思路，题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int getSubPathSum(TreeNode* node, int &res) {
    if(!node) return 0;
    int l = getSubPathSum(node->left, res);
    int r = getSubPathSum(node->right, res);
    res = max(res, node->val + max(0, l) + max(0, r));
    node->val += max(0, max(l, r));
    return node->val;
}
int maxPathSum(TreeNode* root) {
    int res = INT_MIN;
    getSubPathSum(root, res);
    return res;
}

传送门：Binary Tree Maximum Path Sum

Karl