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

1.思路：本题和543.二叉树的直径类似。

（1）链：从下面的某个节点（不一定是叶子节点）到当前节点的路径，这条链的节点值之和即为dfs的返回值。如果节点值之和是负数，则返回0（因为要和0取最大值）。

（2）直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个node，假设直径在这里“拐弯”，也就是计算由左右两条从下面的某个节点（不一定是叶子节点）到node的链的节点值之和，然后去更新答案的最大值。

2.注意：dfs返回的是链的节点值之和，不是直径的节点值之和。

3.疑问：如果节点值都是负数，会得出什么结果？

答：如果所有节点值都是负数，那么就是要求最大节点值（即绝对值最小的负数）。因为在所有节点值都为负数的情况下，路径中只有一个最大节点值（即绝对值最小的负数）是最优的，毕竟随着节点数量的增多，路径和只会减小，此时求出来的最大路径和就是max(nums)。

递归三部曲：

1.确定递归函数的参数和返回值类型：

（1）参数：根节点root。

（2）返回值类型：返回最大路径和，为int类型。

（3）全局变量：ans，记录最大路径和。

private int ans = Integer.MIN_VALUE; public int maxPathSum(TreeNode root)

2.确定终止条件：如果节点为空，则返回0。不存在节点的话最大路径自然是0。

if(node == null){ return 0; }

3.确定单层递归的逻辑：因为求最大路径和要先知道左子树和右子树的链长，因此采用后序遍历的顺序，先递归左右子树，再求最大路径和。

int left = dfs(node.left); int right = dfs(node.right); // 计算全局答案，计算以当前节点为根的最大路径和，因此可以返回两条链 ans = Math.max(ans,left + right + node.val); // 是递归过程，只需返回从左子树或右子树到当前节点的最大路径链给上层，是告诉父节点，从我这个节点往下走，能得到的最大链和是多少 return Math.max(Math.max(left,right) + node.val,0);

复杂度分析：

（1）时间复杂度：O(n)，其中n为二叉树的节点个数。

（2）空间复杂度：O(n)，最坏情况下，二叉树会退化成一条链，递归需要O(n)的栈空间。

附代码：

class Solution { private int ans = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return ans; } private int dfs(TreeNode node){ if(node == null){ return 0; } int left = dfs(node.left); int right = dfs(node.right); // 计算全局答案，计算以当前节点为根的最大路径和，因此可以返回两条链 ans = Math.max(ans,left + right + node.val); // 是递归过程，只需返回从左子树或右子树到当前节点的最大路径链给上层，是告诉父节点，从我这个节点往下走，能得到的最大链和是多少 return Math.max(Math.max(left,right) + node.val,0); } }