二叉树直径 - 更好的设计

algorithm java tree recursion binary-tree

2022-09-03 03:09:08

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

我可以在不使用类级别静态变量的情况下执行此操作吗？

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

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个左，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;
}

答案 2

下面是一个 O（n）解决方案，对接受的答案的更改最小：

public static int[] getDiameter(BinaryTreeNode root) {
    int[] result = new int[]{0,0};    //1st element: diameter, 2nd: height    
    if (root == null)  return result;
    int[] leftResult = getDiameter(root.getLeft());
    int[] rightResult = getDiameter(root.getRight());
    int height = Math.max(leftResult[1], rightResult[1]) + 1;
    int rootDiameter = leftResult[1] + rightResult[1] + 1;
    int leftDiameter = leftResult[0];
    int rightDiameter = rightResult[0];
    result[0] = Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
    result[1] = height;

    return result;
}

它只是同时计算高度和直径。由于Java没有按引用传递，我定义了一个int[]来返回结果。