LeetCode二叉树的最大路径和 [H]递归

124. 二叉树中的最大路径和 - 力扣（LeetCode）

一、题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2   1   3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 20 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

二、代码

1.  
   /**
2.  
   * Definition for a binary tree node.
3.  
   * public class TreeNode {
4.  
   * int val;
5.  
   * TreeNode left;
6.  
   * TreeNode right;
7.  
   * TreeNode() {}
8.  
   * TreeNode(int val) { this.val = val; }
9.  
   * TreeNode(int val, TreeNode left, TreeNode right) {
10.  
    * this.val = val;
11.  
    * this.left = left;
12.  
    * this.right = right;
13.  
    * }
14.  
    * }
15.  
    */
16.  
    class Solution {
17.  
    public class Info{
18.  
    // 从左子树或者右子树延伸出来的连到x节点的最大路径和（注意这个只是从左子树或右子树开始连到x为止的路径，并不是从左子树跨过x再连到右子树的路径）
19.  
    public int maxPathSumFromHead;
20.  
    // 以当前节点为根节点的整棵树的最大路径和（路径并不一定要过x节点）
21.  
    public int maxPathSum;
22.  
     
23.  
    public Info(int maxPathSumFromHead, int maxPathSum) {
24.  
    this.maxPathSumFromHead = maxPathSumFromHead;
25.  
    this.maxPathSum = maxPathSum;
26.  
    }
27.  
    }
28.  
     
29.  
    public int maxPathSum(TreeNode root) {
30.  
    // 无效参数
31.  
    if (root == null) {
32.  
    return 0;
33.  
    }
34.  
     
35.  
    // 返回root的maxPathSum信息
36.  
    return process(root).maxPathSum;
37.  
    }
38.  
     
39.  
    // 二叉树递归
40.  
    public Info process(TreeNode x) {
41.  
    // basecase 空的话直接返回null，让上层去做相关的判断
42.  
    if (x == null) {
43.  
    return null;
44.  
    }
45.  
     
46.  
    // 通过递归获得左右子树的信息
47.  
    Info leftInfo = process(x.left);
48.  
    Info rightInfo = process(x.right);
49.  
     
50.  
    // 1、先计算maxPathSumFromHead。一共就有三种情况：1)只有x 2）x往左扎 3）x往右扎
51.  
    // 先将maxPathSumFromHead初始化为x.val，情况一
52.  
    int maxPathSumFromHead = x.val;
53.  
    // 每一步操作都要先判断leftInfo和rightInfo是否为空
54.  
    // 去比较x往左扎的路径最大值是否是比maxPathSumFromHead大，大则更新maxPathSumFromHead，情况二
55.  
    if (leftInfo != null) {
56.  
    maxPathSumFromHead = Math.max(maxPathSumFromHead, x.val leftInfo.maxPathSumFromHead);
57.  
    }
58.  
    // 去比较x往右扎的路径最大值是否是比maxPathSumFromHead大，大则更新maxPathSumFromHead，情况三
59.  
    if (rightInfo != null) {
60.  
    maxPathSumFromHead = Math.max(maxPathSumFromHead, x.val rightInfo.maxPathSumFromHead);
61.  
    }
62.  
     
63.  
    // 2、再计算以x为根节点的整棵树的最大路径和maxPathSum。
64.  
    // 一共就有六种情况：1) 只有x 2)左树整体的最大路径和（不过x节点，也就是左树的maxPathSum） 3) 右树整体的最大路径和（不过x节点，也就是右树的maxPathSum） 4)从左树连接到x节点的最大路径和（只有x到左树的路径） 5)从右树连接到x节点的最大路径和（只有x到右树的路径） 6)从左树连接到x节点，再延伸到右树的最大路径和
65.  
    // 先将maxPathSum初始化为x.val，情况一
66.  
    int maxPathSum = x.val;
67.  
    // 去比较左子树的最大路径和是否是比maxPathSum大，大则更新maxPathSum，情况二
68.  
    if (leftInfo != null) {
69.  
    maxPathSum = Math.max(maxPathSum, leftInfo.maxPathSum);
70.  
    }
71.  
    // 去比较右子树的最大路径和是否是比maxPathSum大，大则更新maxPathSum，情况三
72.  
    if (rightInfo != null) {
73.  
    maxPathSum = Math.max(maxPathSum, rightInfo.maxPathSum);
74.  
    }
75.  
     
76.  
    // 去比较左子树连接到x的最大路径和是否是比maxPathSum大，大则更新maxPathSum，情况四
77.  
    if (leftInfo != null) {
78.  
    // 这个是利用x.val leftInfo.maxPathSumFromHead求出来的
79.  
    maxPathSum = Math.max(maxPathSum, x.val leftInfo.maxPathSumFromHead);
80.  
    }
81.  
    // 去比较右子树连接到x的最大路径和是否是比maxPathSum大，大则更新maxPathSum，情况五
82.  
    if (rightInfo != null) {
83.  
    maxPathSum = Math.max(maxPathSum, x.val rightInfo.maxPathSumFromHead);
84.  
    }
85.  
    // 去比较左子树连接到x，再跨国x连接到右子树的最大路径和是否是比maxPathSum大，大则更新maxPathSum，情况六
86.  
    if (leftInfo != null && rightInfo != null) {
87.  
    // 这个是利用x.val leftInfo.maxPathSumFromHead rightInfo.maxPathSumFromHead求出来的
88.  
    maxPathSum = Math.max(maxPathSum, x.val leftInfo.maxPathSumFromHead rightInfo.maxPathSumFromHead);
89.  
    }
90.  
     
91.  
    // 返回以当前x节点为根节点的树的Info信息
92.  
    return new Info(maxPathSumFromHead, maxPathSum);
93.  
    }
94.  
    }

三、解题思路 

最大路径和一共有如下几种情况：

1、跟x无关

两种可能性

左树、或者右树上的最大路径和

要左树整体的maxPathSum

要右树整体的maxPathSum

然后取左右两棵树maxPathSum的最大值。

2、跟x有关

有四种可能性

1)只有x自己

2)x只往左扎走出来的最大路径和

3)x只往右扎走出来的最大路径和

4)往两头扎出来的最大路径和

通过分析，我们只需要以x为根节点的整棵树的最大路径和（路径并不一定要过x节点） 以及 从左子树或者右子树延伸出来的连到x节点的最大路径和（注意这个只是从左子树或右子树开始连到x为止的路径，并不是从左子树跨过x再连到右子树的路径）。我们只需要这两个信息，就可以组合出上面讲的所有情况。

这篇好文章是转载于：学新通技术网