二叉树的直径和最大距离问题
作者：Grey
原文地址：
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径（边）长度中的最大值。
题目链接：LeetCode 543. Diameter of Binary Tree
主要思路：
定义如下数据结构
public static class Info { public int maxHeight; // 从当前节点插到最底部最大高度 public int max; // 当前树的直径 public Info(int max, int maxHeight) { this.max = max; this.maxHeight = maxHeight; } } 其中max为当前树的直径，maxHeight为从当前节点插到最底部的最大高度；
假设以 head 为头的二叉树，左树为 left，右树为 right，
接下来开始整理以 head 为头的二叉树直径的可能性：
可能性1，以 head 为头的二叉树的直径可能只来自做左树，即: left.max。
可能性2，以 head 为头的二叉树的直径可能只来自做左树，即: right.max。
可能性3，以 head 为头的二叉树的直径可能只来自做左树，即: right.maxHeight + left.maxHeight。
所以，以 head 为头的二叉树直径最终为上述三种可能性的最大值，即
Math.max(Math.max(right.max,left.max),right.maxHeight + left.maxHeight); 接下来整理以 head 为头，能插到最底部的最大高度的可能性：
可能性1，head 节点能插入到左树最底部的最大高度是left.maxHeight + 1，
可能性2，head 节点能插入到右树最底部的最大高度是right.maxHeight + 1，
以上两种可能性求最大值即可，即
Math.max(left.maxHeight, right.maxHeight) + 1 完整代码如下
class Solution { public static int diameterOfBinaryTree(TreeNode head) { if (head == null) { return 0; } return process(head).max; } public static class Info { public int maxHeight; // 从当前节点插到最底部最大高度 public int max; // 当前树的直径长度 public Info(int max, int maxHeight) { this.max = max; this.maxHeight = maxHeight; } } private static Info process(TreeNode head) { if (head == null) { return new Info(0, 0); } Info left = process(head.left); Info right = process(head.right); int max = Math.max(left.maxHeight + right.maxHeight, Math.max(left.max, right.max)); int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1; return new Info(max, maxHeight); } } 二叉树节点间的最大距离问题
题目链接: 牛客：二叉树节点间的最大距离问题
主要思路：
这个问题和上述问题类似，只不过在求上述问题的时候，我们定义两个节点的距离是以边为准，而本问题是以两个节点之间的节点数量为准，而两个节点之间
边的数量 + 1 = 节点数量 所以我们可以基于上述的问题的代码，方便得到本题的代码，核心代码如下
public static Info process(TreeNode head) { if (head == null) { return new Info(0, 0); } Info left = process(head.left); Info right = process(head.right); int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max)); int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1; return new Info(max, maxHeight); } 和上述问题唯一不同的代码就是如下逻辑，上述问题是
int max = Math.max(left.maxHeight + right.maxHeight, Math.max(left.max, right.max)); 而本题的逻辑是
int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max)); 即边的数量 + 1 = 节点数量
完整代码如下：
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String firstLine = sc.nextLine(); String[] s = firstLine.split(" "); int n = Integer.valueOf(s[0]); int rootVal = Integer.valueOf(s[1]); HashMap<Integer, TreeNode> map = new HashMap<>(); TreeNode root = new TreeNode(); map.put(rootVal, root); //构建二叉树 for (int i = 0; i < n; i++) { String line = sc.nextLine(); String[] str = line.split(" "); int faVal = Integer.valueOf(str[0]); int lchVal = Integer.valueOf(str[1]); int rchVal = Integer.valueOf(str[2]); TreeNode curNode = map.get(faVal); if (lchVal != 0) { TreeNode lch = new TreeNode(); curNode.left = lch; map.put(lchVal, lch); } if (rchVal != 0) { TreeNode rch = new TreeNode(); curNode.right = rch; map.put(rchVal, rch); } } Info info = process(root); System.out.println(info.max); } public static Info process(TreeNode head) { if (head == null) { return new Info(0, 0); } Info left = process(head.left); Info right = process(head.right); int max = Math.max(left.maxHeight + right.maxHeight + 1, Math.max(left.max, right.max)); int maxHeight = Math.max(left.maxHeight, right.maxHeight) + 1; return new Info(max, maxHeight); } private static class TreeNode { int val; TreeNode left; TreeNode right; } private static class Info { int maxHeight; int max; public Info(int max, int maxHeight) { this.max = max; this.maxHeight = maxHeight; } } } 
