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。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)C++17 题解
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); // 只能带一条边上传
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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);