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

---