当需要找出二叉树的直径时,泛型树的直径代码不起作用

pgpifvop  于 2021-07-03  发布在  Java
关注(0)|答案(1)|浏览(259)

几天前,我在学习泛型树时,遇到了一个通用树直径的代码,如下所示:

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

今天我在研究二叉树的时候,我遇到了一个类似的问题,即在二叉树中求直径,但是对于二叉树直径问题给出的解决方案与这个方法不同,有没有办法调整这个代码使它也适用于二叉树?我一直在尝试调整它,使之适用于二叉树,但每次我的代码失败一些测试用例。我没有把我的二叉树代码放在这里,因为我已经编写了多种方法,但是它们都失败了。

wwtsj6pe

wwtsj6pe1#

二叉树是通用树的专用版本[1],因此任何适用于通用树的只读算法也适用于二叉树。
由于查找直径是一个只读操作,因此该算法的工作原理应该基本不变。
唯一的区别是,一般树有一个子树列表,而二叉树只有两个单独的子引用,但这是代码应该很容易适应的一个小细节。
例如,你可以增强二叉树 Node 使用方法初始化以使其看起来像常规树节点:

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.childrennode.getChildren() 在代码里你就完了。
参考文献1:一般树和二叉树的区别

相关问题