java - 二叉树的直径 - 更好的设计

Question

我写了一个代码来计算二叉树的直径。 需要以下方面的建议:

1. 我可以不在类级别使用静态变量来做到这一点吗？

2. 算法好吗/有什么建议吗？

   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;
     }
   }
   

Answer 1

在尝试找到二叉树中两个节点之间的最长路径(直径)时，需要考虑三种情况:

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

通过根的最长路径只是左右子树高度的总和(+1 根不需要，因为树的直径有一个根节点和 1 个左子树，1 个右子树节点将是2)，另外两个可以递归找到:

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

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()); //Removing the +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;
}