LeetCode 124 Binary Tree Maximum Path Sum
LeetCode Tree path Binary sum maximum 124
2023-09-27 14:23:28 时间
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1 / \ 2 3
Return 6
.
思路:本人脑子笨。一開始想了好久都木有思路,仅仅有一个笨办法:把全部的叶子i到叶子节点j的路径都遍历一遍。近期写回溯法用递归用的多,我突然想到了递归能够。用一个全局变量max来存储最大值,然后再求最大连续子序列和。如果我们已经知道了某个节点node的左右子树的最大路径和leftmaxsum。rightmaxsum。那么这个节点node的最大路径和为Math.max(node.val,Math.max(node.val+leftmaxsum,node.val+rightmaxsum));这个节点node的最大路径和仅仅是为了给node的父节点准备的,并不是给node自己准备的。
那么给node准备用啥呢---max。 temp=root.val+leftmaxsum+rightmaxsum; max=max>temp?max:temp; 这样max就能返回当前的最大路径和。代码例如以下:
public class Solution { static int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { max = Integer.MIN_VALUE; PathSum(root); return max; } public int PathSum(TreeNode root) { if(root==null) return 0; int leftmaxsum=0; int rightmaxsum=0; int temp=root.val; if(root.left!=null){ leftmaxsum=Math.max(PathSum(root.left),0); } if(root.right!=null){ rightmaxsum=Math.max(PathSum(root.right),0); } temp=root.val+leftmaxsum+rightmaxsum; max=max>temp?max:temp; return Math.max(root.val,Math.max(root.val+leftmaxsum, root.val+rightmaxsum)); } }
相关文章
- Leetcode: Strobogrammatic Number III
- Leetcode: Binary Tree Maximum Path Sum
- Leetcode: Convert Sorted Array to Binary Search Tree
- leetCode 65.Valid Number (有效数字)
- leetCode 94.Binary Tree Inorder Traversal(二叉树中序遍历) 解题思路和方法
- LeetCode_Construct Binary Tree from Inorder and Postorder Traversal
- 【Leetcode】100. 相同的树(简单)
- [LeetCode] Compare Version Numbers
- [LeetCode] N-Queens II
- [LeetCode] Multiply Strings
- [LeetCode] Validate Binary Search Tree
- [Leetcode] Same Tree
- [LeetCode]剑指 Offer 03. 数组中重复的数字
- 99、【树与二叉树】leetcode ——113. 路径总和 II:回溯法两种版本(C++版本)
- 【LeetCode】257. Binary Tree Paths
- 【LeetCode】114. Flatten Binary Tree to Linked List
- Leetcode 236 Lowest Common Ancestor of a Binary Tree
- 【leetcode】:109. 有序链表转换二叉搜索树
- [LeetCode] 1103. Distribute Candies to People 给人们发糖果
- [LeetCode] 958. Check Completeness of a Binary Tree 检查二叉树的完全性
- [LeetCode] 1028. Recover a Tree From Preorder Traversal 从先序遍历还原二叉树
- [LeetCode] 428. Serialize and Deserialize N-ary Tree N叉搜索树的序列化和去序列化
- [LeetCode] Quad Tree Intersection 四叉树相交
- [LeetCode] 488. Zuma Game 祖玛游戏
- [LeetCode] 158. Read N Characters Given Read4 II - Call multiple times 用Read4来读取N个字符之二 - 多次调用
- [LeetCode] Verify Preorder Serialization of a Binary Tree 验证二叉树的先序序列化
- [LeetCode] 85. Maximal Rectangle 最大矩形