二叉树直径 - 更好的设计

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

这是一个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没有pass-by-reference,我定义了一个int []来返回结果.

Answer 2

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

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

通过根的最长路径只是左和右子树的高度之和+ 1(对于根节点),另外两个可以递归地找到:

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

Answer 3

这是Java中具有O(N)时间复杂性的解决方案.它在计算直径时计算相同递归的高度.参考链接

private class HeightWrapper {
    int height = 0;
}

private int getDiameter_helper(BinaryTreeNode root, HeightWrapper wrapper) {
    if (root == null) {
        return 0; // diameter and height are 0
    }

    /* wrappers for heights of the left and right subtrees */
    HeightWrapper lhWrapper = new HeightWrapper();
    HeightWrapper rhWrapper = new HeightWrapper();

    /* get heights of left and right subtrees and their diameters */
    int leftDiameter = getDiameter_helper(root.left, lhWrapper);
    int rightDiameter = getDiameter_helper(root.right, rhWrapper);

    /* calculate root diameter */
    int rootDiameter = lhWrapper.height + rhWrapper.height + 1;

    /* calculate height of current node */
    wrapper.height = Math.max(lhWrapper.height, rhWrapper.height) + 1;

    /* calculate the diameter */
    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}

public int getDiameter(BinaryTreeNode root) {
    HeightWrapper wrapper = new HeightWrapper();
    return getDiameter_helper(root, wrapper);
}