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);
    }
}