热门文章
 当前位置：技术文章 > 编程面试题 >

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

问题内容：

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

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

问题答案：

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

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