二叉树最长最短问题

一般思路：分为3种情况：在左子树，在右子树，左右子树加头结点
解题流程：确定需要的信息，黑盒获取左右子树信息，返回该层信息，递归

给定一棵二叉树的头节点head，请返回最大搜索二叉子树的大小

3种情况：需要额外信息：左子树中最大搜索二叉子树的头结点，右子树中最大搜索二叉子树的头结点，左子树中的最大值，右子树中的最大值，则左右子树合起来的情况是：

leftSubTressInfo.head == left // 左孩子是左子树中最大搜索二叉子树的头结点
&&rightSubTressInfo.head == right
&& head.value > leftSubTressInfo.max
&& head.value < rightSubTressInfo.min

代码：

public static class ReturnType{
        public int size;
        public Node head;
        public int min;
        public int max;
        
        public ReturnType(int a, Node b,int c,int d) {
            this.size =a;
            this.head = b;
            this.min = c;
            this.max = d;
        }
    }
    
    public static ReturnType process(Node head) {
        if(head == null) {
            return new ReturnType(0,null,Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        Node left = head.left;
        ReturnType leftSubTressInfo = process(left);
        Node right = head.right;
        ReturnType rightSubTressInfo = process(right);
        
        int includeItSelf = 0;
        if(leftSubTressInfo.head == left 
                &&rightSubTressInfo.head == right
                && head.value > leftSubTressInfo.max
                && head.value < rightSubTressInfo.min
                ) {
            includeItSelf = leftSubTressInfo.size + 1 + rightSubTressInfo.size;
        }
        int p1 = leftSubTressInfo.size;
        int p2 = rightSubTressInfo.size;
        int maxSize = Math.max(Math.max(p1, p2), includeItSelf);
        
        Node maxHead = p1 > p2 ? leftSubTressInfo.head : rightSubTressInfo.head;
        if(maxSize == includeItSelf) {
            maxHead = head;
        }
        
        return new ReturnType(maxSize,
                maxHead, 
                Math.min(Math.min(leftSubTressInfo.min,rightSubTressInfo.min),head.value),
                Math.max(Math.max(leftSubTressInfo.max,rightSubTressInfo.max),head.value)); 
    }

二叉树中，一个节点可以往上走和往下走，那么从节点A总能走到节点B。节点A走到节点B的距离为：A走到B最短路径上的节点个数。求一棵二叉树上的最远距离。

3种情况，最长路径在左子树，在右子树，经过头结点联合左右子树。

• 左子树最长路径：左子树高度
• 右子树最长路径：右子树高度
• 经过头结点：左子树高度+右子树高度+1
• 递归

public static class ReturnType{
    public int maxDistance;
    public int h;
        
    public ReturnType(int m, int h) {
        this.maxDistance = m;;
        this.h = h;
    }
}
    
public static ReturnType process(Node head) {
    if(head == null) {
        return new ReturnType(0,0);
    }
    ReturnType leftReturnType = process(head.left); // 获取左子树最大距离
    ReturnType rightReturnType = process(head.right); // 获取右子树最大距离
    int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h;
    int p1 = leftReturnType.maxDistance;
    int p2 = rightReturnType.maxDistance;
    int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance); // 收集该层信息返回给上一层
    int hitself  = Math.max(leftReturnType.h, leftReturnType.h) + 1;
    return new ReturnType(resultDistance, hitself); 
}