给定一棵非空二叉树，从中找出最大路径和。

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

也就是说，这棵二叉树肯定是有节点的，最大路径和可能是多个节点的和也可能是一个节点。

实例一不难看出，最大路径和就是这三个节点的和。但是实例二可能就有点难理解

首先要计算各个节点的最大贡献值，空节点的最大贡献值等于0，非空节点的最大贡献值等于本身节点值加上子节点的值，如果有两个子节点，则选取最大的，叶子节点的最大贡献值等于其节点值。

这里我画了张图来理解理解

现在所有的贡献值都已经找完了，最大路径和此时是右子树的左节点15。然后开始回溯，向上找退回到20这个节点，此时price_newpath = left_gain + right_gain + node.val = 15 + 7 + 20 = 42 > 15，更新max_sum。

然后继续回溯，向上找到-10这个根节点，price_newpath = left_gain + right_gain + node.val = 9 + 35 -10 = 34 < 42，不更新max_sum。

可能会觉得35是从哪来的，前边也说过，最大贡献值等于本身节点值加上子节点的值，如果有两个子节点，则选取最大的，所以20这个节点的最大贡献值就等于15 + 20 = 30,根节点的最大贡献值就等于-10 + 35 = 25。

下面来看代码：

LeetCode124 二叉树中的最大路径和