CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

    • 二叉树理论基础
    • 二叉树的四种遍历方法
    • 如何构造一棵二叉树
    • 序列化与反序列化二叉树
    • 左叶子之和
    • 找树左下角的值
    • 二叉树每层的最大值
    • 二叉树的右侧视图
    • 二叉树的锯齿形层序遍历
    • 翻转二叉树
    • 合并二叉树
    • 二叉树剪枝
    • 对称二叉树
    • 另一棵树的子树
    • 剑指 Offer 26 - 树的子结构
    • 寻找重复的子树
    • 二叉树的最大深度
    • 二叉树的最小深度
    • 二叉树的最大宽度
    • 完全二叉树的节点个数
    • 往完全二叉树添加节点
    • 二叉树的完全性检验
    • 平衡二叉树
    • 二叉树的最近公共祖先
    • 最大二叉树
    • 从中序与后序遍历序列构造二叉树
    • 从前序与中序遍历序列构造二叉树
    • 节点之和最大的路径
      • 📃 题目描述
      • 🔔 解题思路
      • 💥 复杂度分析
    • 二叉树的直径
    • 二叉搜索树

    • TreeSet 和 TreeMap

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 二叉树
小牛肉
2022-04-22
目录

节点之和最大的路径

# 📃 题目描述

题目链接:

  • 剑指 Offer II 051. 节点之和最大的路径 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
  • 124. 二叉树中的最大路径和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

# 🔔 解题思路

主要就是抓住一个点:如果某个节点作为路径的起点,那么就不能同时走到它的左右孩子,只能走其中一边

这里注意区分下某个节点的贡献值(以该节点为【起点】的最大路径和)和最大路径和(以该节点为【拐点】的最大路径和)的概念

比如:

  1
 /  \
2	 3

节点 1 的贡献值(以 1 为起点的最大路径和)是1 + Math.max(1 的左孩子为起点的最大路径和(1 的左孩子的贡献值),以 1 的右孩子为起点的最大路径和(1 的右孩子的贡献值))= 1, + Math.max(2,3) = 4

而以 1 为拐点的最大路径和是 以 1 的左孩子为起点的最大路径和(1 的左孩子的贡献值) + 1 + 以 1 的右孩子为起点的最大路径和(1 的右孩子的贡献值)

我们的目的就是,找到路径和最大的那个拐点

所以,典型的后序遍历

class Solution {
    // 存储最大路径和
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 经过当前节点 root 并前往其左子树或右子树的路径的节点值之和的最大值
        maxGain(root);

        return maxSum;
    }

    // 返回 cur 的贡献值(以 cur 为起点的最大路径和)
    private int maxGain(TreeNode cur) {
        if (root == null) {
            return 0;
        }
        
        // 这一段 corner case 可以不写
        // if (cur.left == null && cur.right == null) {
        //     res = Math.max(res, cur.val);
        //     return cur.val;
        // }
        
        // 以 cur.left 为起点的路径和最大值
        // 注意这里不要和 Integer.MIN_VALUE 比较,因为负数也 > MIN_VALUE,但是负数显然对最大路径和没有帮助
        // 所以,只有在最大贡献值大于 0 时,才会选取对应子节点
        int leftGain = Math.max(0, maxGain(cur.left));
        // 以 cur.right 为起点的路径和最大值
        int rightGain = Math.max(0, maxGain(cur.right));
        
        // 以 cur 为拐点的路径和
        int sum = leftGain + cur.val + rightGain;
        // 最大路径和
        maxSum = Math.max(maxSum, sum);
		
        // 返回 cur 的贡献值(以 cur 为起点的最大路径和)
        return cur.val + Math.max(leftGain, rightGain);
    }
}

# 💥 复杂度分析

  • 空间复杂度:O(LogN),取决于树的高度
  • 时间复杂度:O(N),对每个节点访问不超过 2 次

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
从前序与中序遍历序列构造二叉树
二叉树的直径

← 从前序与中序遍历序列构造二叉树 二叉树的直径→

最近更新
01
我掏出这个多线程轮子,面试官直接全体起立
04-13
02
面试官问你有其他 Offer 吗,该怎样回答
04-10
03
天不生陈志龙,职场万古如长夜
04-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式