当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和

题目描述

124 Binary Tree Maximum Path Sum
https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

  1. Input: [1,2,3]
  2. 1
  3. / \
  4. 2 3
  5. Output: 6

Example 2:

  1. Input: [-10,9,20,null,null,15,7]
  2. -10
  3. / \
  4. 9 20
  5. / \
  6. 15 7
  7. Output: 42

相似题目

LeetCode.687.Longest Univalue Path 二叉树的最长同值路径
LeetCode.543.Diameter of Binary Tree 二叉树的直径
LeetCode.124.Binary Tree Maximum Path Sum 二叉树的最大路径和


解题过程

2020年2月

递归过程中更新全局变量
递归函数 treeSum(TreeNode root) 返回以 root为起点的最大路径和,则
treeSum(r) = max(根, 左+根, 右+根)
全局变量sum = max(根, 左+根, 右+根, 左+右+根, sum)

时间复杂度 O(n),空间复杂度 O(n)

  1. private static class SolutionV2020 {
  2. private int sum;
  3. public int maxPathSum(TreeNode root) {
  4. sum = Integer.MIN_VALUE;
  5. treeSum(root);
  6. return sum;
  7. }
  8. // 返回 以root为起点的最大路径和
  9. private int treeSum(TreeNode root) {
  10. if (null == root) {
  11. return 0;
  12. }
  13. int left = treeSum(root.left);
  14. int right = treeSum(root.right);
  15. // res = max(根, 左+根, 右+根)
  16. int res = Math.max(left + root.val, right + root.val);
  17. res = Math.max(res, root.val);
  18. // sum = max(根, 左+根, 右+根, 左+右+根, sum)
  19. sum = Math.max(sum, res);
  20. sum = Math.max(sum, left + root.val + right);
  21. return res;
  22. }
  23. }

2020年6月

递归实现,递归函数 dfs(TreeNode root) 返回 root, root+left, root+right 三者中的最大值,也就是以 root 为起点的单边路径的最大和
维护一个全局最大值 max,表示经过每个结点的路径和最大值,dfs 过程中计算经过当前根节点的路径和最大值,动态更新全局最大值 max

时间复杂度 O(n),空间复杂度 O(n),空间复杂度是因为递归用到栈

  1. private static class SolutionV202006 {
  2. int max = Integer.MIN_VALUE; // 经过每个节点的路径和最大值
  3. public int maxPathSum(TreeNode root) {
  4. max = Integer.MIN_VALUE;
  5. dfs(root);
  6. return max;
  7. }
  8. // 深度优先遍历二叉树 root,返回 root, root+left, root+right 三者中的最大值,即以 root 为起点的单边路径的最大和,过程中更新全局最大值 max
  9. private int dfs(TreeNode root) {
  10. if (null == root) {
  11. return 0;
  12. }
  13. int curMax = root.val; // 经过当前根节点的路径和最大值
  14. int leftMax = dfs(root.left); // 左子树单边路径的最大值
  15. curMax += Math.max(leftMax, 0);
  16. int rightMax = dfs(root.right); // 右子树单边路径的最大值
  17. curMax += Math.max(rightMax, 0);
  18. max = Math.max(curMax, max); // 更新全局最大值
  19. return Math.max(root.val, Math.max(root.val + leftMax, root.val + rightMax));
  20. }
  21. }

GitHub代码

algorithms/leetcode/leetcode/_124_BinaryTreeMaximumPathSum.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_124_BinaryTreeMaximumPathSum.java


上一篇 V2Ray

下一篇 LeetCode.687.Longest Univalue Path 二叉树的最长同值路径

阅读
评论
647
阅读预计3分钟
创建日期 2020-02-01
修改日期 2020-06-21
类别

页面信息

location:
protocol: http:
host: masikkk.com
hostname: masikkk.com
origin: http://masikkk.com
pathname: /article/LeetCode.124.BinaryTreeMaximumPathSum/
href: http://masikkk.com/article/LeetCode.124.BinaryTreeMaximumPathSum/
document:
referrer:
navigator:
platform: Linux x86_64
userAgent: Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)

评论