二叉树节点间的最大距离问题

1. 当前节点不参与路径，此时左右子树中最大路径较大的那个就是当前节点不参与路径时的最长路径。如上图红色节点（根节点）的子树中，最长路径就是两个黄色节点经过蓝色节点的路径，并未经过红色节点自身。
2. 当前节点参与路径，此时最大的路径应该是：左树高+右树高+1（1为当前节点）。如上图中蓝色节点的子树中，最长路径就是两个黄色节点经过自己的那条路径。

1. 计算以当前节点为根节点的子树高度：height=max(left_height, right_height)+1
2. 以当前节点为根节点的子树所包含的最大路径长度：max(左子树最大路径, 右子树最大路径, 左树高+右树高+1)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

// 信息体结构
class Info {
    public int maxDistance;      // 最大距离
    public int height;           // 树高
    public Info(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]);
        // 构建树
        HashMap<Integer, TreeNode> map = new HashMap<>();
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int val = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(val);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 树形DP
        Info info = process(root);
        System.out.println(process(root).maxDistance);
    }
    
    private static Info process(TreeNode root) {
        if(root == null)
            return new Info(0, 0);
        Info leftInfo = process(root.left);        // 左树信息
        Info rightInfo = process(root.right);      // 右树信息
        // 经过头节点的路径
        int path1 = leftInfo.height + rightInfo.height + 1;
        // 不经过头结点的路径
        int path2 = Math.max(leftInfo.maxDistance, rightInfo.maxDistance);    // 左右子树中路径大的那个
        return new Info(Math.max(path1, path2), Math.max(leftInfo.height, rightInfo.height) + 1);
    }
}

        /**
     * 1. 最长距离不路过root，
     * 2. 最长距离路过root
     * @param root
     * @return
     */
    public static int maxDistance(TreeNode root){
        if (root == null){
            return 0 ;
        }
        //每个节点的最大距离分为上述的两种情况
        //这里需要重复的计算节点的高度
        return Math.max(height(root.left)+height(root.right)+1 ,
                Math.max(maxDistance(root.left) , maxDistance(root.right))) ;
    }

    public static int height(TreeNode root){
        if (root == null){
            return 0 ;
        }
        if (root.left == null && root.right == null){
            return 1 ;
        }
        return Math.max(height(root.left) , height(root.right))+1 ;
    }