二叉树的直径 - 更好的设计 [英] Diameter of Binary Tree - Better Design

问题描述

我已经写了code查找二叉树的直径。 需要进行如下的建议：

1. 在我能做到这一点，而不使用静态变量的类层次？

2. 是算法精/有什么建议？

    公共类DiameterOfTree {
   公共静态INT直径= 0;
   公共静态INT getDiameter（BinaryTreeNode根）{
       如果（根！= NULL）{
           INT leftCount = getDiameter（root.getLeft（））;
           INT rightCount = getDiameter（root.getRight（））;
           如果（leftCount + rightCount＆GT;直径）{
               直径= leftCount + rightCount;
               的System.out.println（---直径-------------＆gt;中+直径）;
           }
           如果（leftCount＆GT; rightCount）{
               返回leftCount + 1;
           }
           返回rightCount + 1;
       }
       返回0;
     }
   }
    

解决方案

有三种情况下试图找到一个二叉树两个节点之间的最长路径（直径）时要考虑的：

1. 的最长路径穿过根，
2. 的最长路径完全包含在左子树，
3. 的最长路径完全包含在右子树。

通过根的最长路径是简单的左和右子树+ 1的高度之和（对于根节点），而另外两个可以递归发现：

 公共静态INT getDiameter（BinaryTreeNode根）{
    如果（根== NULL）
        返回0;

    INT rootDiameter =的getHeight（root.getLeft（））+的getHeight（root.getRight（））+ 1;
    INT leftDiameter = getDiameter（root.getLeft（））;
    INT rightDiameter = getDiameter（root.getRight（））;

    返回Math.max（rootDiameter，Math.max（leftDiameter，rightDiameter））;
}

公共静态INT的getHeight（BinaryTreeNode根）{
    如果（根== NULL）
        返回0;

    返回Math.max（的getHeight（root.getLeft（）），的getHeight（root.getRight（）））+ 1;
}
 

I have written a code for finding diameter of Binary Tree. Need suggestions for the following:

1. Can I do this without using static variable at class level?

2. Is the algorithm fine/any suggestions?

   public class DiameterOfTree {   
   public static int diameter = 0; 
   public static int getDiameter(BinaryTreeNode root) {        
       if (root != null) {                     
           int leftCount = getDiameter(root.getLeft());
           int rightCount = getDiameter(root.getRight());
           if (leftCount + rightCount > diameter) {
               diameter = leftCount + rightCount;
               System.out.println("---diameter------------->" + diameter);
           }           
           if ( leftCount > rightCount) {
               return leftCount + 1;
           }
           return rightCount + 1;
       }
       return 0;
     }
   }
   

解决方案

There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):

1. The longest path passes through the root,
2. The longest path is entirely contained in the left sub-tree,
3. The longest path is entirely contained in the right sub-tree.

The longest path through the root is simply the sum of the heights of the left and right sub-trees + 1 (for the root node), and the other two can be found recursively:

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()) + 1;
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public static int getHeight(BinaryTreeNode root) {
    if (root == null)
        return 0;

    return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
}

这篇关于二叉树的直径 - 更好的设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！