一、题目

　　二叉树中，一个节点可以往上走和往下走，那么从节点A总能走到节点B。

　　节点A走到节点B的距离为:A走到B最短路径上的节点个数。

　　求一颗二叉树上的最远距离

二、思路

　　利用递归分别求出每个节点的左右子树中的最大距离，和该节点的高度。

三、代码实现

1 public class MaxDistanceInTree { 2      3     public static class Node{ 4         public int value; 5         public Node left; 6         public Node right; 7          8         public Node(int value) { 9             this.value = value;10         }11     }12     13     public static class ReturnType{14         public int maxDistance;15         public int h;16         17         public ReturnType(int maxDistance, int h) {18             this.maxDistance = maxDistance;19             this.h = h;20         }21     }22     23     public static ReturnType process(Node head){24         if(head==null){25             return new ReturnType(0, 0);26         }27         ReturnType leftReturnType = process(head.left);28         ReturnType rightReturnType = process(head.right);29         int includeHeadDistance = leftReturnType.h+1+rightReturnType.h;30         int p1 = leftReturnType.maxDistance;31         int p2 = rightReturnType.maxDistance;32         int resDistance = Math.max(Math.max(p1, p2), includeHeadDistance);33         int hitselef = Math.max(leftReturnType.h, rightReturnType.h)+1;//自身高度34         return new ReturnType(resDistance, hitselef);35     }36     37     public static int maxDistance(Node head){38         int [] record = new int[1];39         return posOrder(head, record);40     }41     42     public static int posOrder(Node head,int[] record){43         if(head==null){44             record[0] = 0;45             return 0;46         }47         int lMax = posOrder(head.left, record);48         int maxFromLeft = record[0];49         int rMax = posOrder(head.right, record);50         int maxFromRight = record[0];51         int curNodeMax = maxFromLeft+maxFromRight+1;52         record[0] = Math.max(maxFromLeft, maxFromRight)+1;//当前节点的高度53         return Math.max(Math.max(lMax, rMax), curNodeMax);54     }55     56     public static void main(String[] args) {57         /**58          *                       159          *                  2           360          *               4    5      6      761          *           8                 962          */63         Node head1 = new Node(1);64         head1.left = new Node(2);65         head1.right = new Node(3);66         head1.left.left = new Node(4);67         head1.left.right = new Node(5);68         head1.right.left = new Node(6);69         head1.right.right = new Node(7);70         head1.left.left.left = new Node(8);71         head1.right.left.right = new Node(9);72         System.out.println(maxDistance(head1));73         74         75         Node head2 = new Node(1);76         head2.left = new Node(2);77         head2.right = new Node(3);78         head2.right.left = new Node(4);79         head2.right.right = new Node(5);80         head2.right.left.left = new Node(6);81         head2.right.right.right = new Node(7);82         head2.right.left.left.left = new Node(8);83         head2.right.right.right.right = new Node(9);84         System.out.println(maxDistance(head2));85     }86 }