leetcode ：124 二叉树最大路径和
题目
hard 难度
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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
解题思路
用一个int 变量 记录每次找到的路径和来递归比对 后序遍历二叉树，算出每一个二叉树的和放入res 每一个树与每一个数对比 递归方法返回单个子树的最大路径和，求出左右两边子树的单条最大路径和反复对比
代码执行思路如下
小冷把每次递归的值都已经debug好，在下面是每次递归的次数
以上述案例二为例子：
代码语言：javascript复制第一次递归 => root = 9 left = null right=null
第二次递归 => root = 15 left = null right=null
第三次递归 => root = 7 left = null right=null
第四次递归 => root = 20 left = 15 right=7 res = 42 单条最大为 15 20 =35
第五次递归 => root = -10 left = 9 right= 35 计算的递归结果返回的最大子树的路径和
最后 对比是 35 <42 res是42代码
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 考虑负数 要考虑比较负值，所以用最小int
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null){
return 0;
}
getTreeNodeMaxNum(root);
return res;
}
// 递归寻找左右最大路径方法
public int getTreeNodeMaxNum(TreeNode root){
// 非空
if(root == null){
return 0;
}
//递归找到左子树最大值
int leftMaxNum = Math.max(0,getTreeNodeMaxNum(root.left)); // 9
//这里先算出子树的 此时子树的结果是42
//之后回到root =-10的栈中 letf = 9 right = 35
int rightMaxNum = Math.max(0,getTreeNodeMaxNum(root.right));
// 后续遍历 最后输出root
int maxpathNum = root.val leftMaxNum rightMaxNum;
// 因为是递归寻找，所以我们还有找到res 和
//每次子树找到的最大路径和 maxpathNum比较
//之后在这里判断 （34，42） = 42
res = Math.max(res,maxpathNum);
// 算出单条路径最大值的公式
return Math.max(leftMaxNum,rightMaxNum) root.val;
}
}提交结果
