Binary tree maximum distance, diameter of binary tree

May 29, 2015

Diameter of binary tree: The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree.

Read two websites:

http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html

http://www.geeksforgeeks.org/diameter-of-a-binary-tree/

copy Java code solution from the website:

http://blog.csdn.net/fightforyourdream/article/details/16843303

1.  /**
2.      * 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter)
3.      * 递归解法： 
4.      * （1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
5.      * （2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，
6.      * 要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，
7.      * 同时记录左子树和右子树节点中到根节点的最大距离。
8.      * 
9.      * http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html
10.      * 
11.      * 计算一个二叉树的最大距离有两个情况:
13.         情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
14.         情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
15.         只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离
16.      */
17.     public static Result getMaxDistanceRec(TreeNode root){
18.         if(root == null){
19.             Result empty = new Result(0, -1);       // 目的是让调用方 +1 后，把当前的不存在的 (NULL) 子树当成最大深度为 0
20.             return empty;
21.         }
23.         // 计算出左右子树分别最大距离
24.         Result lmd = getMaxDistanceRec(root.left);
25.         Result rmd = getMaxDistanceRec(root.right);
27.         Result res = new Result();
28.         res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1;        // 当前最大深度
29.         // 取情况A和情况B中较大值
30.         res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );
31.         return res;
32.     }
34.     private static class Result{
35.         int maxDistance;
36.         int maxDepth;
37.         public Result() {
38.         }
40.         public Result(int maxDistance, int maxDepth) {
41.             this.maxDistance = maxDistance;
42.             this.maxDepth = maxDepth;
43.         }
44.     }