LeetCode124-二叉树中的最大路径和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-tree-maximum-path-sum/

中文链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

题目详述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

1
2
3
4
5
6
7
输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

1
2
3
4
5
6
7
8
9
输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

题目详解

本题与 LeetCode112-路径总和、LeetCode113-路径总和II 和 LeetCode437-路径总和III 的路径定义全都不同，它的路径被定义为一条从树中任意节点出发，达到任意节点的序列。

  • 当前二叉树的最大路径和，来源于以下三个组成部分：
    • 当前结点，记为 ①。
    • 当前结点的左子树的单边的最大路径，记为 ②。
    • 当前结点的右子树的单边的最大路径，记为 ③。
  • 这三者的可能的组合为：
    • ①。
    • ②。
    • ③。
    • ① + ②。
    • ① + ③。
    • ① + ② + ③。
    • 其中只含 ② 或只含 ③ 的组合可以在递归的过程中可以被其他组合覆盖掉，我们只用考虑其他四种组合。对 ② 和 0 作比较，取其中较大值；同理，对 ③ 做同样的处理，这四种组合可以统一为 ① + ② + ③ 这一种组合。
  • 为了方便，我们需要计算从当前 root 往下的一条单边最大路径和。
  • 这样，我们可以在递归的过程中，更新最大路径和。
  • 需要注意的是，本题是递归返回的值并不是我们要求的结果的典型题型。在本题中，递归返回的值是从当前结点往下的单边的路径和，而要求的结果是从一结点出发到任意结点的最大路径和，这需要我们在递归的过程中不断更新，这一点需要仔细体会。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00124 {

    public int maxPathSum(TreeNode root) {
        int[] res = new int[] {root.val};
        dfs(root, res);
        return res[0];
    }

    private int dfs(TreeNode root, int[] res) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, dfs(root.left, res));
        int right = Math.max(0, dfs(root.right, res));
        res[0] = Math.max(res[0], root.val + left + right);
        return root.val + Math.max(left, right);
    }
}