package com.binaryTree;

/** 路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列.
 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
 路径和 是路径中各节点值的总和。
 给你一个二叉树的根节点 root ,返回其 最大路径和 。
 链接:https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

 * */
public class TreeMaxPathSum {

 public class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;
 TreeNode() {}
 TreeNode(int val) {
 this.val = val;
 }
 TreeNode(int val, TreeNode left, TreeNode right) {
 this.val = val;
 this.left = left;
 this.right = right;
 }
 }
 public static class Info{
 private int maxPathSum;

 public Info(int maxPathSum) {
 this.maxPathSum = maxPathSum;
 }
 }
 public static int maxPathSum(TreeNode root) {
 return process(root).maxPathSum;
 }

 public static Info process(TreeNode node){
 if (node == null){
 return new Info(0);
 }
 Info leftInfo = process(node.left);
 Info rightInfo = process(node.right);

 int left = leftInfo.maxPathSum;
 int right = rightInfo.maxPathSum;
 // 将符合条件的最大路径和 是否与头结点有关作为可能性分类的标准
 // 可能性1: 最大路径和与当前的头结点 有关, 路径经过头结点
 // 可能性2: 最大路径和 与 当前的头节点 无关,路径不经过头结点

 int p2 = 0;
 int p3 = 0;
 int p1= node.val;
 p2 = Math.max(node.val,node.val + Math.max(left,right)); //
 p3 = Math.max(p2,node.val + left +right); // 路径经过头结点

 int res = Math.max(node.val,p3);
 return new Info(res);
 }
}