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好，在下面是每次递归的次数
以上述案例二为例子：
第一次递归 => 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
代码
/** * 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; } }
提交结果
