【每日一题】leetcode hard难度：二叉树最大路径和

冷环渊

发布于 2022-02-10 08:00:20

1810

发布于 2022-02-10 08:00:20

文章被收录于专栏：冷环渊的全栈工程师历程

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;
  }
}

提交结果