【题目】
从二叉树的节点A出发，可以向上走或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫作A到B的距离。
【分析】
以X为头结点的子树，总共3种情况，
1、左子树 最大距离为 整棵树的最大距离
2、右子树 最大距离为 整棵树的最大距离
3、整棵树的最大距离为 左子树高度 + 右子树高度 + 1
package zyc.binaryTree;public class P168_MaxDistance {/*** 以X为头结点的子树，总共3种情况，* 1、左子树 最大距离为 整棵树的最大距离* 2、右子树 最大距离为 整棵树的最大距离* 3、整棵树的最大距离为 左子树高度 + 右子树高度 + 1*/public static ReturnType getMaxDistance(Node node) {if (node == null) {return new ReturnType(0, 0);}ReturnType left = getMaxDistance(node.left);ReturnType right = getMaxDistance(node.right);int maxDistance = Math.max((left.height + right.height + 1), Math.max(left.maxDistance, right.maxDistance));int height = Math.max(left.height, right.height) + 1;return new ReturnType(maxDistance, height);}public static class ReturnType {public int maxDistance;public int height;public ReturnType(int maxDistance, int height) {this.maxDistance = maxDistance;this.height = height;}}public static void main(String[] args) {Node node = new Node(1);node.left = new Node(2);node.left.left = new Node(4);node.left.right = new Node(5);node.right = new Node(3);node.right.right = new Node(7);node.right.left = new Node(6);ReturnType maxDistance = getMaxDistance(node);System.out.println(maxDistance.maxDistance);}public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}}