Tuesday, June 9, 2015

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:
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.      * 计算一个二叉树的最大距离有两个情况:
  12.         情况A: 路径经过左子树的最深节点,通过根节点,再到右子树的最深节点。
  13.         情况B: 路径不穿过根节点,而是左子树或右子树的最大距离路径,取其大者。
  14.         只需要计算这两个情况的路径距离,并取其大者,就是该二叉树的最大距离
  15.      */
  16.     public static Result getMaxDistanceRec(TreeNode root){
  17.         if(root == null){
  18.             Result empty = new Result(0, -1);       // 目的是让调用方 +1 后,把当前的不存在的 (NULL) 子树当成最大深度为 0
  19.             return empty;
  20.         }
  21.         // 计算出左右子树分别最大距离
  22.         Result lmd = getMaxDistanceRec(root.left);
  23.         Result rmd = getMaxDistanceRec(root.right);
  24.         Result res = new Result();
  25.         res.maxDepth = Math.max(lmd.maxDepth, rmd.maxDepth) + 1;        // 当前最大深度
  26.         // 取情况A和情况B中较大值
  27.         res.maxDistance = Math.max( lmd.maxDepth+rmd.maxDepth, Math.max(lmd.maxDistance, rmd.maxDistance) );
  28.         return res;
  29.     }
  30.     private static class Result{
  31.         int maxDistance;
  32.         int maxDepth;
  33.         public Result() {
  34.         }
  35.         public Result(int maxDistance, int maxDepth) {
  36.             this.maxDistance = maxDistance;
  37.             this.maxDepth = maxDepth;
  38.         }
  39.     }

No comments:

Post a Comment