package com.jiucaiyuan.net.algrithm.tree;



/**

 * 树形dp套路

 * <p>

 * 树形dp套路使用前提：

 * 如果题目求解目标是S规则，则求解流程可以定成每一个节点为头节点的子树

 * 在S规则下的每个答案，并且最终答案一定在其中

 * <p>

 * 案例题

 * 【题目】二叉树节点间的最大距离

 * 从二叉树的节点a出发，可以向上或者向下走，但是沿途节点只能经过一次，

 * 到达节点b时路径上节点的个数叫做a到b的距离，那么二叉树任意两个节点

 * 之间都有距离，求整棵树上的最大距离

 * 【思路】

 * 划分为三种情况：

 * 1.头结点参与，最大可能是左树高+1+右树高

 * 2.头结点不参与，左树最大距离

 * 3.头结点不参与，右树最大距离

 * 从三种中选择最大值，就是整棵树的最大距离

 *

 * @Author jiucaiyuan  2022/5/6 23:06

 * @mail services@jiucaiyuan.net

 */



public class MaxDistanceInTree {

    public static class Info {

        public int maxDistance;

        public int height;



        public Info(int dis, int h) {

            this.maxDistance = dis;

            this.height = h;

        }

    }



    /**

     * 取得以head为头结点的整棵树最大距离

     *

     * @param head 树的头结点

     * @return head树的最大距离

     */

    public static int maxDistance(Node head) {

        return process(head).maxDistance;

    }



    /**

     * 返回以head为头结点的整棵树的信息

     *

     * @param head

     * @return

     */

    private static Info process(Node head) {

        if (head == null) {

            return new Info(0, 0);

        }

        //向左子树要信息

        Info left = process(head.left);

        //向右子树要信息

        Info right = process(head.right);

        //最大距离根据头结点是否参与分成三种情况，三种情况最大值，是本结点的最大距离

        int dis = Math.max(Math.max(left.maxDistance, right.maxDistance), left.height + 1 + right.height);

        //树的高度是左子树和右子树较大的+1

        int h = Math.max(left.height, right.height) + 1;

        return new Info(dis, h);

    }

}