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

我写了一个代码来查找二叉树的直径。
需要以下建议:

是否可以在类级别使用静态变量而不这样做？

算法是否正确/有任何建议？

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

最佳答案

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

最长的路径穿过根

最长的路径完全包含在左侧子树

中

最长的路径完全包含在右侧的子树中。

穿过根的最长路径只是左右子树的高度之和(对于根来说，+ 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;
}

关于java - 二叉树的直径-更好的设计，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11897088/