LeetCode124
2022/4/21 6:18:57
本文主要是介绍LeetCode124,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目地址
参考思路
题目:路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
路径:从一个节点到另一个节点的路径
路径和:从一个起始节点出发 的的所有路径的最大和
你可以选择树中的任意节点作为起始节点
但是起始节点只能选一个!即你最终选择的所有路径全部是从一个起始节点出发
以上图为例说明地柜过程:
我们用题目的示例来描述一下这个算法过程:(理解如何递归很关键)
- 从 dfs(-10) 开始,
1.1 dfs(9): 1.1.1 左孩子为空;贡献为 0 1.1.2 右孩子为空,贡献为 0 1.1.3 更新 res = max (-∞,(9 + 0 + 0)) = 9 1.1.4 返回 dfs(9) = 9 + max(左孩子贡献,右孩子贡献)) = 9 1.2 dfs(20) 1.2.1 dfs(15): 1.2.1.1 左孩子为空;贡献为0 1.2.1.2 右孩子为空,贡献为0 1.2.1.3 更新 res = max(9, 15 + 0 + 0) = 15 1.2.1.4 返回 dfs(15) = 15 + 0 = 15 1.2.2 dfs(7): 1.2.2.1 左孩子为空;贡献为 0 1.2.2.2 右孩子为空,贡献为 0 1.2.2.3 更新 res = max(15, 7 + 0 + 0) = 15 1.2.2.4 返回 dfs(7) = 7 + 0 = 7 1.2.3 更新 res = max (15, 20 + dfs(15) + dfs(7) ) = 42 1.2.4 返回dfs(20) = 20 + max(15, 7) = 35 1.3 更新 res = max(42, -10 + dfs(9) + dfs(20) ) = max(42, 34) = 42 1.4 返回 dfs(-10) = -10 + max(9, 35) = 25 (当然这一步就没啥用了,已经有最终res)
所以最大路径和 res = 42
关键就是区分:
- 当前节点最大路径和计算:以当前节点为起点的所有路径和
- 当前节点对上一层的贡献:只能选择当前节点的最大的一条路径作为贡献,因为路径节点不可重复
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { if (root == null) { return 0; } dfs(root); return res; } public int dfs(TreeNode root) { if (root == null) { return 0; } /** Q:左右孩子贡献为什么要大于等于0? A: 因为计算从某一节点出发的路径和的时候,计算公式为: 当前节点值 + 左孩子贡献 + 右孩子贡献, 而左右孩子贡献是「可选的」,也就是说当某一边贡献小于0的时候,我可以在计算路径和时不算这一边 这种情况也就相当于其贡献为 0,但是注意路径和至少包含「当前节点的值」。 **/ int leftMax = Math.max(0, dfs(root.left)); // 左孩子贡献 int rightMax = Math.max(0, dfs(root.right)); // 右孩子贡献 res = Math.max(res, root.val + leftMax + rightMax); // 更新res return root.val + Math.max(leftMax, rightMax); // 返回当前节点的总贡献 }
}
这篇关于LeetCode124的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置