LeetCode-124-二叉树中的最大路径和

124. 二叉树中的最大路径和

难度困难

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

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

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

示例 1：

img

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

示例 2：

img

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

提示：

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

解题思路

和head无关

image-20210610100150745

和head有关

• 和head有关情况一 只包含head自己

image-20210610100547264

• 和head有关情况二 head+左(maxpath)

image-20210610101400401

• 和head有关情况三 x+右(必含右head出发的maxpath)

image-20210610102431435

• 和head有关情况四 head+左((必含左树head出发的maxpath)+右(必含右树head出发的maxpath)

image-20210610102749404

需要左右子数提供信息，然后递归

public static class Info {
   public int maxPathSum;
   public int maxPathSumFromHead;

   public Info(int path, int head) {
      maxPathSum = path;
      maxPathSumFromHead = head;
   }
}

public static int maxPathSum(TreeNode root) {
   if (root == null) {
      return 0;
   }
   return process(root).maxPathSum;
}


public static Info process(TreeNode x) {
   if (x == null) {
      return null;
   }
   Info leftInfo = process(x.left);//递归获取左树的路径和head路径maxpath
   Info rightInfo = process(x.right);//递归获取右树的路径和head路径maxpath
   int p1 = Integer.MIN_VALUE;
   if (leftInfo != null) {
      p1 = leftInfo.maxPathSum;//左和
   }
   int p2 = Integer.MIN_VALUE;
   if (rightInfo != null) {
      p2 = rightInfo.maxPathSum;//右和
   }
   int p3 = x.val;//只含X
   int p4 = Integer.MIN_VALUE;
   if (leftInfo != null) {
      p4 = x.val + leftInfo.maxPathSumFromHead;//x+左(maxpath)
   }
   int p5 = Integer.MIN_VALUE;
   if (rightInfo != null) {
      p5 = x.val + rightInfo.maxPathSumFromHead;//x+右(maxpath)
   }
   int p6 = Integer.MIN_VALUE;
   if (leftInfo != null && rightInfo != null) {
      p6 = x.val + leftInfo.maxPathSumFromHead + rightInfo.maxPathSumFromHead;//和head有关情况四 head+左((必含左树head出发的maxpath)+右(必含右树head出发的maxpath)
   }
   int maxSum = Math.max(Math.max(Math.max(p1, p2), Math.max(p3, p4)), Math.max(p5, p6));
   int maxSumFromHead = Math.max(p3, Math.max(p4, p5));//x x+左(maxpath) x+右(maxpath) pk一个最大值
   return new Info(maxSum, maxSumFromHead);
}

image-20210610103232634