首页 > 其他分享 >Leecode热题100-104.二叉树中的最大路径和

Leecode热题100-104.二叉树中的最大路径和

时间:2024-11-08 20:21:31浏览次数:3  
标签:maxPathEndWithRoot val 路径 maxPath Leecode 二叉树 TreeNode 100 root

二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 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

提示:

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000
/**
 * 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 {
    /**对于二叉树的一般问题我想到的都是二叉树的递归套路,对于本题来说看起来也行
    最大路径和可能出现的三个地方:1. 左树 2. 右树 3.包含根(这里可以认为是只有根或者左右数和根还有左右树经过根跨到对方的所有情况的合集)
    其实仔细想想就知道只要我们知道左右树的两个信息就能拿下:1.最大路径和 2.以根结尾的最大路径(左右子树的最大路径以根结尾才能和根以及自己的兄弟关联)
    因为我们找左右子树都要一下这个信息,综合了就是自己的信息 
    也许这些信息不够,或许我们还需要一个最大路径不包含根的,但是没事我们先试试看,不行再加呗
    */
    public int maxPathSum(TreeNode root) {
        Info info = getInfo(root);
        return info.maxPath;
    }

    public Info getInfo(TreeNode root) {
        if(root == null) {
            return null;
        }
        /**如果左右孩子都没有,就返回自己的val作为maxPath和maxPathEndWithRoot */
        if(root.left == null && root.right == null) {
            return new Info(root.val, root.val);
        }
        /**拿到左右子树的信息*/
        Info leftInfo = getInfo(root.left);
        Info rightInfo = getInfo(root.right);
        /**定义当前节点关于Info的两个信息,暂时设置为自己的val */
        int maxPath = root.val;
        int maxPathEndWithRoot = root.val;
        if(leftInfo != null) {
            maxPathEndWithRoot = Math.max(maxPathEndWithRoot, leftInfo.maxPathEndWithRoot + root.val);
            maxPath = Math.max(maxPath, Math.max(leftInfo.maxPath, root.val + leftInfo.maxPathEndWithRoot));
        }
        if(rightInfo != null) {
            maxPathEndWithRoot = Math.max(maxPathEndWithRoot, rightInfo.maxPathEndWithRoot + root.val);
            maxPath = Math.max(maxPath, Math.max(rightInfo.maxPath, root.val + rightInfo.maxPathEndWithRoot));
        }
        /**最大路径还可以是跨越左右树的 */
        maxPath = Math.max(maxPath, (leftInfo != null && leftInfo.maxPathEndWithRoot>0? leftInfo.maxPathEndWithRoot : 0) + 
            (rightInfo != null && rightInfo.maxPathEndWithRoot>0? rightInfo.maxPathEndWithRoot : 0) + root.val);
        return new Info(maxPath, maxPathEndWithRoot);

    }

    static class Info {
        int maxPath;
        int maxPathEndWithRoot;
        public Info(int maxPath, int maxPathEndWithRoot) {
            this.maxPath = maxPath;
            this.maxPathEndWithRoot = maxPathEndWithRoot;
        }
    }
}

标签:maxPathEndWithRoot,val,路径,maxPath,Leecode,二叉树,TreeNode,100,root
From: https://blog.csdn.net/Chang_Yafei/article/details/143634219

相关文章

  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的intg......
  • 二叉树遍历
    二叉树遍历这个问题,以前一直没搞懂,只是模糊的了解。先序遍历:先访问根节点,再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点,再访问根节点,最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树,再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
  • 20241009 模拟赛
    20241009模拟赛A.排列喵手玩一下,依次操作\(1,n,1\)必然能使序列有序,所以答案不超过\(3\)。那么依次判断\(0,1,3\)即可。原序列如果有序就是\(0\)。如果\(a_1=n\)且\(a_n=1\)就是\(3\),因为这两个条件有一个不满足时只要操作\(1,n\)或\(n,1\)就能变成有序。考虑......
  • 20241006 CF977
    20241006CF977A.MeaningMean题意:给定一个序列,每次选两个数变成平均值,使最后结果最大。感性理解,一个数被平均次数越多,最终贡献减小的越多(不考虑取整,被平均了\(cnt\)次,就乘上\(2^{-cnt}\))。那么肯定让小数平均多次,于是排序后按顺序做就是最优解。B.MaximizeMex题意:给定......
  • 20241004 动态规划选讲
    20241004动态规划选讲P6669[清华集训2016]组合数问题使用Lucas定理:\(C_n^m\equivC_{\lfloor\frac{n}{p}\rfloor}^{\lfloor\frac{m}{p}\rfloor}C_{n\bmodp}^{m\bmodp}(\bmodp)\)。这等价于将\(n,m\)在\(k\)进制下的每一位的组合数相乘。要想使\(k\|\C_n^m\),就......
  • 20241002 模拟赛
    20241002模拟赛Ainv容易想到按\(s\)中\(0\)和\(1\)的连续段将原序列分段考虑。显然大的数放前面最好。于是按值从大到小,段从前往后分配值,\(0\)的段降序,\(1\)的段升序即可完成构造。求逆序对可以直接树状数组。但这题每个不同\(01\)段之间都有大小关系,于是每段中的......
  • Python从0到100(七十):Python OpenCV-Opencv实现人像迁移
    前言:零基础学Python:Python从0到100最新最全教程。想做这件事情很久了,这次我更新了自己所写过的所有博客,汇集成了Python从0到100,共一百节课,帮助大家一个月时间里从零基础到学习Python基础语法、Python爬虫、Web开发、计算机视觉、机器学习、神经网络以及人工智能相关知......
  • 二叉树 (王道数据结构 C语言版)
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件:写完了递归算法,运行的时......
  • 100_api_intro_text_chinesepinyin
    中文转拼音API数据接口多音字智能解析,毫秒级响应,拼音标准格式。1.产品功能多音字智能解析;拼音标准格式;毫秒级响应性能;全接口支持HTTPS(TLSv1.0/v1.1/v1.2/v1.3);全面兼容AppleATS;全国多节点CDN部署;接口极速响应,多台服务器构建API接口负载均衡;接口调用状......