当前位置 : 首页 » 文章分类 :  算法  »  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:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   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)

private static class SolutionV2020 {
    private int sum;
    public int maxPathSum(TreeNode root) {
        sum = Integer.MIN_VALUE;
        treeSum(root);
        return sum;
    }

    // 返回 以root为起点的最大路径和
    private int treeSum(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int left = treeSum(root.left);
        int right = treeSum(root.right);
        // res = max(根, 左+根, 右+根)
        int res = Math.max(left + root.val, right + root.val);
        res = Math.max(res, root.val);
        // sum = max(根, 左+根, 右+根, 左+右+根, sum)
        sum = Math.max(sum, res);
        sum = Math.max(sum, left + root.val + right);
        return res;
    }
}

2020年6月

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

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

private static class SolutionV202006 {
    int max = Integer.MIN_VALUE; // 经过每个节点的路径和最大值
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        dfs(root);
        return max;
    }

    // 深度优先遍历二叉树 root,返回 root, root+left, root+right 三者中的最大值,即以 root 为起点的单边路径的最大和,过程中更新全局最大值 max
    private int dfs(TreeNode root) {
        if (null == root) {
            return 0;
        }
        int curMax = root.val; // 经过当前根节点的路径和最大值
        int leftMax = dfs(root.left); // 左子树单边路径的最大值
        curMax += Math.max(leftMax, 0);
        int rightMax = dfs(root.right); // 右子树单边路径的最大值
        curMax += Math.max(rightMax, 0);
        max = Math.max(curMax, max); // 更新全局最大值
        return Math.max(root.val, Math.max(root.val + leftMax, root.val + rightMax));
    }
}

GitHub代码

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


上一篇 LeetCode.700.Search in a Binary Search Tree 在BST中搜索

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

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

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论