转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4253605.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：如果我们把二叉树看成一个图，一棵树显示是一颗有向无环图，定义"距离"为两节点之间边的个数(不考虑方向)。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。
题目分析：《编程之美》一书上提供了这样一种思路：计算一个二叉树的最大距离有两个情况:
- 情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
- 情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。
注：求得的距离大小是唯一的，但是路径却不一定唯一。
算法设计：
定义节点的数据结构，有数据，左孩子，有孩子，左边最大深度，右边最大深度。
//节点的数据结构 private static class Node { public int data; public Node left; //指向左子树 public Node right; //指向右子树 public int leftDepth; //左边的最大长度 public int rightDepth; //右边的最大长度 public Node() { super(); // TODO Auto-generated constructor stub } public Node(int data, Node left, Node right, int leftDepth, int rightDepth) { super(); this.data = data; this.left = left; this.right = right; this.leftDepth = leftDepth; this.rightDepth = rightDepth; } }
构造二叉树，传入根节点。
1.如果节点为空则结束。
2.若左(右)孩子为空，则让该节点的左(右)最大深度为0。
3.如果左子树不为空，递归求左子的树节点之间的最大距离。
4.如果右子树不为空，递归求右子的树节点之间的最大距离。
5.如果左子树不为空，则root的左边深度+1。
6.如果右子树不为空，则root的右边深度+1。
7.更新最长距离。
java实现源码：
1 package com.interview; 2 3 4 /** 5 * 题目：求二叉树中节点的最大距离... 6 * @author wjh 7 * 8 */ 9 public class _11_1MaxDistance { 10 11 /** 12 * @param args 13 */ 14 public static int maxdistance=0; 15 public static void main(String[] args) { 16 int[] a = {20,5,4,3,2,7,13,11};//{20,5,22,4,7,25,13,36,42,11,24}; 17 Node root = null; 18 root = createTree( root, a); //1)建树 19 maxDistance(root); //2)求该树的节点间的最大距离 20 System.out.println("该二叉树的节点的最大距离为："+maxdistance); 21 } 22 23 24 //求树的节点之间的最大距离 25 private static void maxDistance(Node root){ 26 if(root==null){ //如果节点为空则结束 27 return; 28 } 29 //点的左右最大深度已经初始化为0 30 if(root.left!=null){ //1)如果左子树不为空，递归求左子树节点之间的最大距离 31 maxDistance(root.left); 32 } 33 if(root.right!=null){ //2)如果右子树不为空，递归求右子树节点之间的最大距离 34 maxDistance(root.right); 35 } 36 if(root.left!=null){ //3)如果左子树不为空，则root的左边深度+1 37 int tempDistance = max(root.left.leftDepth,root.left.rightDepth); 38 root.leftDepth = tempDistance+1; 39 } 40 if(root.right!=null){ //4)如果右子树不为空，则root的右边深度+1 41 int tempDistance = max(root.right.leftDepth,root.right.rightDepth); 42 root.rightDepth = tempDistance+1; 43 } 44 int distance = root.leftDepth+root.rightDepth; 45 if(distance>maxdistance){ //5)更新最长距离 46 maxdistance = distance; 47 } 48 } 49 50 51 //创建二叉排序树 52 public static Node createTree(Node root, int[] r){ 53 int n = r.length; 54 System.out.println("建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):"); 55 for(int i=0;i<n;i++){ 56 Node child = new Node(r[i],null,null,0,0);//点的左右最大深度已经初始化为0 57 root = insert(root, child); 58 } 59 return root; 60 } 61 62 //二叉排序树的插入算法 63 public static Node insert(Node root, Node child){ 64 //寻找插入位置 65 if(root==null){ 66 root = child; 67 System.out.println(root.data); 68 } 69 else 70 if(root.data>child.data){ 71 System.out.print(root.data+"<--");//在root左边插入 72 root.left = insert(root.left, child); 73 } 74 else{ 75 System.out.print(root.data+"-->"); //在root右边插入 76 root.right = insert(root.right,child); 77 } 78 return root; 79 } 80 81 82 //求两个数中的较大的 83 private static int max(int a, int b){ 84 return (a>=b?a:b); 85 } 86 87 //节点的数据结构 88 private static class Node { 89 public int data; 90 public Node left; //指向左子树 91 public Node right; //指向右子树 92 public int leftDepth; //左边的最大长度 93 public int rightDepth; //右边的最大长度 94 public Node() { 95 super(); 96 // TODO Auto-generated constructor stub 97 } 98 99 public Node(int data, Node left, Node right, int leftDepth, 100 int rightDepth) { 101 super(); 102 this.data = data; 103 this.left = left; 104 this.right = right; 105 this.leftDepth = leftDepth; 106 this.rightDepth = rightDepth; 107 } 108 } 109 110 }
运行结果：
建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):
20
20<--5
20<--5<--4
20<--5<--4<--3
20<--5<--4<--3<--2
20<--5-->7
20<--5-->7-->13
20<--5-->7-->13<--11
该二叉树的节点的最大距离为：6
拓展：
博客园另一位博友(http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html)的提供了这样一种思路：
情况A 及 B 需要不同的信息: A 需要子树的最大深度，B 需要子树的最大距离。只要函数能在一个节点同时计算及传回这两个信息，代码就可以很简单:
节点的数据结构：
//节点的数据结构 private static class Node { public int data; public Node left; //指向左子树 public Node right; //指向右子树 public Node() { super(); // TODO Auto-generated constructor stub } public Node(int data, Node left, Node right) { super(); this.data = data; this.left = left; this.right = right; } }
结果数据结构：
//结果的数据结构 private static class Result{ public int maxDistance; public int maxDepth; public Result() { super(); // TODO Auto-generated constructor stub } public Result(int maxDistance, int maxDepth) { super(); this.maxDistance = maxDistance; this.maxDepth = maxDepth; } }
求节点距离的算法设计及算法实现：
1.如果root 为空，则返回{0,-1}
2. 递归求左右子树的result.
3.当前节点的最大距离为 [左右子树的最大距离] 与 [ 左右子树最大深度之和+2] 的最大值;当前节点的最大为左右子树最大深度+1.
1 //求节点最大距离 2 private static Result maxDistance(Node root){ 3 if(root==null){ //1)如果root 为空，则返回empty 4 Result empty = new Result(0,-1); 5 return empty; 6 } 7 Result left = maxDistance(root.left);//2) 递归求左右子树的result 8 Result right = maxDistance(root.right); 9 //3)当前节点的最大距离为左右子树的最大距离与左右子树最大深度+2 的最大值; 10 //当前节点的最大为左右子树最大深度+1 11 int thisDistance = max(max(left.maxDistance,right.maxDistance), 12 left.maxDepth+right.maxDepth+2); 13 int thisDepth = max(left.maxDepth,right.maxDepth)+1; 14 Result empty = new Result(thisDistance,thisDepth); 15 return empty; 16 }
可以看到在进入节点时，如果节点为 NULL，会传回一个 empty 变量。比较奇怪的是 empty.maxDepth = -1，目的是让叶子节点的左右子树都为空，当叶子节点调用函数将maxDepth +1 后，把叶子节点的最大深度置为 0。
完整的java实现源码：
1 package com.interview; 2 3 4 /** 5 * 题目：求二叉树中节点的最大距离... 6 * @author wjh 7 * 8 */ 9 public class _11_2MaxDistance { 10 11 /** 12 * @param args 13 */ 14 public static void main(String[] args) { 15 int[] a = {20,5,4,3,2,7,13,11};//{20,5,22,4,7,25,13,36,42,11,24}; 16 Node root = null; 17 root = createTree( root, a); //1)建树 18 Result result = maxDistance(root); //2)求该树的节点间的最大距离 19 System.out.println("该二叉树的节点的最大距离为："+result.maxDistance); 20 21 } 22 23 //求节点最大距离 24 private static Result maxDistance(Node root){ 25 if(root==null){ //1)如果root 为空，则返回empty 26 Result empty = new Result(0,-1); 27 return empty; 28 } 29 Result left = maxDistance(root.left);//2) 递归求左右子树的result 30 Result right = maxDistance(root.right); 31 //3)当前节点的最大距离为左右子树的最大距离与左右子树最大深度+2 的最大值; 32 //当前节点的最大为左右子树最大深度+1 33 int thisDistance = max(max(left.maxDistance,right.maxDistance), 34 left.maxDepth+right.maxDepth+2); 35 int thisDepth = max(left.maxDepth,right.maxDepth)+1; 36 Result empty = new Result(thisDistance,thisDepth); 37 return empty; 38 } 39 40 //创建二叉排序树 41 public static Node createTree(Node root, int[] r){ 42 int n = r.length; 43 System.out.println("建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):"); 44 for(int i=0;i<n;i++){ 45 Node child = new Node(r[i],null,null);//点的左右最大深度已经初始化为0 46 root = insert(root, child); 47 } 48 return root; 49 } 50 51 //二叉排序树的插入算法 52 public static Node insert(Node root, Node child){ 53 //寻找插入位置 54 if(root==null){ 55 root = child; 56 System.out.println(root.data); 57 } 58 else 59 if(root.data>child.data){ 60 System.out.print(root.data+"<--");//在root左边插入 61 root.left = insert(root.left, child); 62 } 63 else{ 64 System.out.print(root.data+"-->"); //在root右边插入 65 root.right = insert(root.right,child); 66 } 67 return root; 68 } 69 70 71 //求两个数中的较大的 72 private static int max(int a, int b){ 73 return (a>=b?a:b); 74 } 75 76 //节点的数据结构 77 private static class Node { 78 public int data; 79 public Node left; //指向左子树 80 public Node right; //指向右子树 81 public Node() { 82 super(); 83 // TODO Auto-generated constructor stub 84 } 85 public Node(int data, Node left, Node right) { 86 super(); 87 this.data = data; 88 this.left = left; 89 this.right = right; 90 } 91 } 92 //结果的数据结构 93 private static class Result{ 94 public int maxDistance; 95 public int maxDepth; 96 public Result() { 97 super(); 98 // TODO Auto-generated constructor stub 99 } 100 public Result(int maxDistance, int maxDepth) { 101 super(); 102 this.maxDistance = maxDistance; 103 this.maxDepth = maxDepth; 104 } 105 } 106 }
运行结果：
建树过程(a<--b表示在a左边插入b;a-->b表示在a右边插入b):
20
20<--5
20<--5<--4
20<--5<--4<--3
20<--5<--4<--3<--2
20<--5-->7
20<--5-->7-->13
20<--5-->7-->13<--11
该二叉树的节点的最大距离为：6