当需要找出二叉树的直径时，通用树的直径代码不起作用

Question

前几天在学习泛型树的时候，偶然发现了一个泛型树直径的代码如下：

 static int diameter = Integer.MIN_VALUE;
  public static int findDia(Node node){
      int dch = -1; // dch = deepest child height
      int sdch =-1; // sdch = second deepest child height
      
      for(Node child : node.children){ // children of current node are in an arraylist , every node has data + reference of arraylist of its children
          int ch = findDia(child); // ch = child height
          if(ch>dch){
              sdch=dch;
              dch=ch;
          }else if(ch>sdch){
              sdch=ch;
          }
      }
      if(sdch+dch+2>diameter){
          diameter = sdch+dch+2;
      }
      return dch+1;
  }

今天在学习二叉树的时候，遇到了一个类似的问题，即求二叉树的直径，但是二叉树直径问题给出的解决方案与这种方法不同，有没有办法调整这个代码以便它也适用于二叉树？我一直在尝试调整它以使其适用于二叉树，但每次我的代码都无法通过某些测试用例。我没有把我的二叉树代码放在这里，因为我写了多种方法，但它们都没有通过一些测试用例。

Answer 1

二叉树是通用树特殊版本^[1],所以任何适用于通用树的只读算法也适用于二叉树。

由于查找直径是只读操作，因此算法应该几乎没有变化。

唯一的区别是通用树有一个子节点列表，而二叉树只有 2 个单独的子节点引用，但这是代码应该很容易适应的次要细节。

你可以，例如使用一种方法增强二叉树 Node class 使其看起来像一般树节点：

Node[] getChildren() {
    if (this.left == null) {
        if (this.right == null)
            return new Node[0];
        return new Node[] { this.right };
    }
    if (this.right == null)
        return new Node[] { this.left };
    return new Node[] { this.left, this.right };
}

现在将代码中的 node.children 替换为 node.getChildren() 就大功告成了。

^{参考1： Difference between General tree and Binary tree}

当需要找出二叉树的直径时，通用树的直径代码不起作用

Code for diameter of generic tree not working when required to find out diameter of binary tree

java

tree

recursion

binary-tree

data-structures