南昌网站制作方案定制,wordpress 百度收录,渲模网,佛山外包网站建设题目
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#xff0c;且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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
解决思路
解决方法 private var finalMax Int.MIN_VALUEfun maxPathSum(root: TreeNode?): Int {dfs(root)return finalMax}fun dfs(root: TreeNode?): Int {if (root null) {return 0}//左右两个子节点贡献值最小为0 如果是负数那么就直接不归属相当于取0val maxLeft dfs(root.left).coerceAtLeast(0)val maxRight dfs(root.right).coerceAtLeast(0)var max (maxRight root.val).coerceAtLeast(maxLeft root.val)//当前节点当作整个路径的最大值计算一下finalMax finalMax.coerceAtLeast(maxLeft maxRight root.val)//返回的max表示当前节点的最大贡献值return max}核心是注意当前节点的最大路径与当前节点作为子节点时的贡献是两个不同的值当前节点的最大路径 max(自己自己左边自己右边自己 左边 右边
当前节点作为子节点时的贡献max(自己自己左边自己右边
后者相对前者少了左右都存在的情况。因为作为子节点时一条路如果同时包含左右
根就被包含了2次不符合题目只出现一次的限制了。总结
1.最近有些懈怠了人还是需要鞭策的。 不然总是耗费大量时间玩游戏就不好了
2.这道题说难也不难只是当时自己没有完全想明白咋回事。 还是看了题解做出来了。
3.才思泉涌的人让我见个吧。真没见过多聪明的人。 高斯爱因斯坦这种
4.人上了年纪真的会又些好吃的没法吃了。 因为会掉牙。真咬不动。 切记古人的忠告树欲停 而风不止 子欲养 而亲不待 父母恩情其实基本上儿女是回报不了的 父母把全部心血给了自己 自己成为父母后却不能把全部心血还给父母 因为还要培养下一代 就这样 恩情在一代代流传
