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

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

- Manish

---

“is the algorithm fine?”的意思是算法可行吗？你测试过代码了吗？ - arunmoezhi

Arun，当然我已经测试过代码了。我的意思是说，是否有更好的算法？ - Manish

这个问题也可以在[CodeReview.SE]上得到很好的解答。 - S.L. Barth

@Barth，谢谢。我不知道有代码审查这个功能。我也会去试试看。 - Manish

@Manish 哦，好的。请参考这个链接：http://www.geeksforgeeks.org/archives/5687 - arunmoezhi

除了面试之外，找到二叉树的直径还有其他用途吗？ - Jeff

Answer 1

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

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

通过根节点的最长路径仅仅是左子树和右子树高度的总和（因为有根节点并且1个左子树、1个右子树节点的树的直径将是2，因此不必+1），可以递归地找到另外两个情况：

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

- verdesmarald

---

@Harshdeep，是的，它的复杂度是O(n^2)，因为它每次都要遍历到底部才能找到高度。我正在寻找在同一遍历中计算高度和直径的代码。 - AKS

你把高度和节点混淆了，高度是“边数”，因此只有一个节点的树的高度为0。从技术上讲，你的代码是正确的，但术语不太准确。 - JavaDeveloper

根据这段代码，这棵树的直径是4: a -> b -> c -> d但是，唯一的叶节点是d。因此，树的直径被定义为两个叶子之间最长路径的长度，因此直径应该是1。 - kirakun

@kirakun，在这种情况下直径不应该是0（或根到叶子的长度乘以2）吗？ - unknown_boundaries

rootDiameter应该是左子树高度和右子树高度之和。因为只有两个节点的树的直径为1。 int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()); - Ermias K

Answer 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[] 来返回结果。

- Niki

---

这行代码 int[] rightResult = getDiameter(root.getLeft()); 可能应该改为：int[] rightResult = getDiameter(root.getRight());？ - Patrizio Rullo

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

- nem035

---

+1 .. 感谢您提供的解决方案。为什么我们需要将它们放在包装类中呢？ 我已经查看了链接，但是我无法在Java中实现相同的功能。但是您的解决方案似乎可以正常工作。您能否编辑上面的答案并解释为什么我们需要一个包装类？ - Amarnath

嗨@Che，你需要一个包装类的原因是Java是按值传递的，这意味着使用一个对象包装器来维护数据值是通过递归级别正确维护值的最简单方法。这里有另一个有用的链接：https://dev59.com/EXVD5IYBdhLWcg3wQJOT - nem035

对于只有一个节点的树，你的代码会给出直径为1，这是错误的。在这种情况下应该是0。 - Aditya Joshee

嗯，一个节点是一种情况，你可以争论0或1都可能是有效答案。这完全取决于你在计算直径时是否将起始节点计入考虑的定义中。 - nem035

Answer 4

您不需要将结果存储在静态字段diameter中。只需像这样使用静态方法：

public class DiameterOfTree {

    public static long getDiameter(BinaryTreeNode root) {
        if (root != null) {
            long leftDiameter = getDiameter(root.getLeft());
            long rightDiameter = getDiameter(root.getRight());
            long leftHeight = getHeight(root.getLeft());
            long rightHeight = getHeight(root.getRight());
            return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
        }
        return 0;
    }

    public static long getHeight(BinaryTreeNode root) {
        if (root != null) {
            long leftHeight = getHeight(root.getLeft());
            long rightHeight = getHeight(root.getRight());
            return  1 + Math.max(leftHeight, rightHeight);
        }
        return 0;
    }
}

- Xavier Delamotte

---

这并不是给你直径，而是给你深度。 - Keppil

@Xavier，你能提供一个优化版本的代码吗？它可以在同一递归中计算高度，这样就不必一直到底部才能计算高度了。这样复杂度将从O(n^2)降至O(n)。 - AKS

@AKS，你可以牺牲时间来获得空间，并添加记忆化以实现线性时间复杂度（因为每个节点的高度可以从其子树的结果中以O(1)时间计算出来）。或者，你可以使用一次后序遍历（可迭代地完成，而不必使用递归）并存储这些结果。 - rliu

Answer 5

相对于被接受的答案，有一个最小的O(n)答案。

int DiameterTree(BinaryTreeNode root, int diameter) {
    int left, right;
    if (!root) return 0;

    left  = DiameterTree(root.getLeft(), diameter);
    right = DiameterTree(root.getRight(), diameter);
    if (left + right > diameter) diameter = left + right;

    return Math.max(left, right) + 1;
}

假设 diameter 是一个类中的静态变量。

- shakirthow

---

你为什么在方法参数中使用 diameter 作为普通变量？ - roottraveller

请您能否解释一下这个算法？我无法理解在返回语句中添加1的概念。 - Learner

Answer 6

一棵树T的直径为

直径(T) = max( 直径(T.左子树), 直径(T.右子树), 高度(T.左子树)+高度(T.右子树)+1 )

注：直径是指树中任意两个节点之间最长路径的长度。

 private class Data {  
   public int height;  
   public int diameter;  
 }  

 private void diameter(TreeNode root, Data d) {  
   if (root == null) {  
     d.height = 0; d.diameter = 0; return;  
   }  
   diameter(root.left, d); // get data in left subtree  
   int hLeft = d.height;  
   int dLeft = d.diameter;  
   diameter(root.right, d); // overwrite with data in right tree  
   d.diameter = Math.max(Math.max(dLeft, d.diameter), hLeft+d.height+1);  
   d.height = Math.max(hLeft, d.height) + 1;  
 }  

 public int diameter(TreeNode root) {  
   Data data = new Data();  
   diameter(root, data);  
   return data.diameter;  
 }  

- Snehal Masne

Answer 7

public class NodeWrap{
    int height = 0;
    int maxLength = 0;
    public NodeWrap(int h, int m){
        height = s;
        maxLength = m;
    }
}


public NodeWrap getDiameter(BinaryNode root){
    if(root == null){
        return new NodeWrap(0, 0);
    }

    NodeWrap left = getDiameter(root.left);
    NodeWrap right = getDiameter(root.right);

    int height = Math.max(left.height + right.height) + 1;

    int maxLength = Math.max(left.maxLength, right.maxLength);
    if(left.height != 0 && right.height != 0){
        maxLength = Math.max(left.height + right.height + 1, maxLength);
    }
    return new NodeWrap(singleLength, maxLength);
}

- ChrisBangle

---

你能回答OP发布的问题吗？他并没有要求提供其他代码。 - banarun

Answer 8

One more O(n) solution in python,
code is self explanatory, only issue with this code is it returns tuple containing both height and diameter of the tree. 

def diameter(node, height):
  if node is None:
    return 0, 0
  leftheight  = 0
  rightheight = 0
  leftdiameter,  leftheight = diameter(node.left, leftheight)
  rightdiameter, rightheight = diameter(node.right, rightheight)
  rootheight = 1 + max(leftheight, rightheight ) 
  rootdiameter = ( leftheight + rightheight + 1 )
  return max( rootdiameter, leftdiameter, rightdiameter ), rootheight

- Shashank Shandilya

Answer 9

这里是一个使用C++编写的递归解决方案，可以给出二叉树的高度和直径。

struct tree
{
    int height = -1;
    int diameter = 0;
};

struct tree BSTDiameter(struct node *root)
{
    struct tree currentTree, leftTree, rightTree;
    if (root == NULL)
    {
        currentTree.height = -1;
        currentTree.diameter = 0;
        return currentTree;
    }
    leftTree = BSTDiameter(root->left);
    rightTree = BSTDiameter(root->right);
    currentTree.height = ((leftTree.height > rightTree.height) ? leftTree.height : rightTree.height) + 1;
    if (leftTree.height == -1 || rightTree.height == -1)
        currentTree.diameter = 0;
    else
        currentTree.diameter = (leftTree.height + rightTree.height + 3) > (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter) ? (leftTree.height + rightTree.height + 3) : (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter);
    return currentTree;
}

这个的时间复杂度是O(h)，其中h是树的高度。 希望这能帮到你。

- Rishab Dhawan

Answer 10

简洁明了的解决方案：

// way to use below util function:
prop p = new prop();
diameterUtil(root, p);
System.out.println(p.d);

class prop {
    int h;
    int d;
}

private void diameterUtil(Node n, prop p) {
    if (n == null) {
        p.h = 0;
        p.d = 0;
        return;
    }
    prop lp = new prop();
    prop rp = new prop();
    diameterUtil(n.left, lp);
    diameterUtil(n.right, rp);
    p.h = Math.max(lp.h, rp.h) + 1;
    p.d = Math.max((lp.h + rp.h + 1), Math.max(lp.d, rp.d));
}

- arora