HHot 100C++ 图解

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

困难 二叉树 在力扣上做

一句话套路DFS 只返回「单边贡献」,答案全局取 max

题目描述

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和 。

 

示例 1:

输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6

示例 2:

输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42

 

提示:

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

思路

时间O(n)
空间O(h)

区分两个量(本题的难点全在这里)

· 链贡献 gain(n)

从 n 出发还能往「上」延伸给父亲用,只能二选一,

所以是 n->val + max(左, 右),并且负贡献要截断为 0。

· 路径答案

在 n 处「拐弯」,左 + n + 右,只能在此刻更新全局答案,无法上传。

全负树

答案必须是最大的那个负数,所以初值是 INT_MIN 而不是 0。

图解

9 -10 15 20 7
二叉树(来自本仓库测试数据,nullopt 表示空位)

C++17 题解

src/08_binary_tree.cpp19 行
namespace lc0124 {
class Solution {
 public:
  int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    gain(root, best);
    return best;
  }

 private:
  static int gain(TreeNode* n, int& best) {
    if (!n) return 0;
    int l = max(0, gain(n->left, best));   // 负收益的子树直接不要
    int r = max(0, gain(n->right, best));
    best = max(best, l + r + n->val);      // 在 n 处拐弯的完整路径
    return n->val + max(l, r);             // 只能带一条边上传
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q124_max_path_sum13 行
lc0124::Solution s;
TreeNode* a = buildTree({-10, 9, 20, nullopt, nullopt, 15, 7});
CHECK_EQ(s.maxPathSum(a), 42);  // 15 -> 20 -> 7
freeTree(a);
TreeNode* b = buildTree({1, 2, 3});
CHECK_EQ(s.maxPathSum(b), 6);
freeTree(b);
TreeNode* c = buildTree({-3});  // 全负
CHECK_EQ(s.maxPathSum(c), -3);
freeTree(c);
TreeNode* d = buildTree({2, -1});
CHECK_EQ(s.maxPathSum(d), 2);  // 宁可只取根
freeTree(d);

↑↓ 选择↵ 打开/ 随时唤起