题目描述 给定一个非空二叉树，返回其最大路径和。 本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。 示例 1: 输入: [1,2,3] 1 / \ 2 3 输出: 6 示例 2: 输入: [-10,9,20,null,null,15,7]   -10    / \   9  20     /  \    15   7 输出: 42 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/ 解法1 – DFS（超时） 刚遇到题目时没有什么思路，根据题目描述“本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。”，发现这很像图数据结构的DFS算法。 我们可以把树转换为无向图，这通过向TreeNode数据结构添加Parent字段就能够实现。这样，每个节点有三个临接点分别是左子树、右子树、父节点。 我们从树中寻找val大于0的节点作为DFS的起点，从所有的起点出发遍历完这棵树，肯定能找到包含答案的路径。我们累积走过的每一个定点的值，用当前累积的值更新全局变量result，result就存放了最终的答案。 很遗憾，上面的方法虽然能够找到正确的答案，但是效率太低。我一时也没有找到这种方法的优化思路，先记录下来。 解法2 方法2来自于该题目的评论区。思路是：节点n向父节点汇报以下三者中的最大值；如果节点n是叶节点则仅汇报节点n自身的值。 节点n的值 节点n的值+节点n左子树汇报的值 节点n的值+节点n右子树汇报的值 我们以图2为例，红色字体给出的是节点向其父节点按照上述规则汇报的值。注意，图2与图1不相同。 有了上面的图，我们把图中每个顶点“臆想”成该顶点就是整颗树的根节点，而忽略掉该节点之上的其他节点。然后我们对每个“臆想”的根节点，按照以下规则计算出的最大值。 根节点的值 根节点的值+左子树汇报的值 根节点的值+右子树汇报的值 根节点的值+左子树汇报的值+右子树汇报的值 因为我们把每个节点“臆想”成根节点，我们才会有上面规则的第4条。需要注意的是，该问题的解并不一定来源于整颗树的根节点。我们想个反例，把图2的根节点5的值调整为-∞，那么解应该来源于节点8.…