二叉树最大路径和题解

题解思路

我们可以使用深度优先搜索（DFS）的方式来递归求解。
对于每个节点，设其最大贡献值（即以该节点为起点、延伸到一侧分支上的最大路径和）为：

max_gain = node.val + max(左子树的贡献, 右子树的贡献, 0)

这里，当左右子树的贡献为负时，我们可以选择不连接（视作0），因为负数会降低路径和。

同时，节点 node 作为“拐点”时，能够形成的路径和为：

Leetcode 50.二叉树中的最大路径和-原题链接

题目内容

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

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

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

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

一个整数，表示最大路径和。

样例1

输入

1 2 3

输出

6

说明

最优路径是$2 -> 1 -> 3$ ，路径和为 $2 + 1 + 3 = 6$

样例2

输入

-10 9 20 null null 15 7

输出

42

说明

最优路径是$15 -> 20 -> 7$ ，路径和为 $15 + 20 + 7 = 42$

提示

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