Блог

Несколько дней назад я изучал общие деревья и наткнулся на код для диаметра общего дерева следующим образом :

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

Сегодня, когда я изучал двоичные деревья, я столкнулся с аналогичным вопросом, т.Е. Найти диаметр в двоичном дереве, но решение, данное для вопроса о диаметре двоичного дерева, отличается от этого подхода, есть ли способ настроить этот код так, чтобы он работал и для двоичного дерева? Я пытался настроить его так, чтобы он работал для двоичного дерева, но каждый раз, когда мой код не проходит какой-либо тестовый пример. Я не поместил здесь свой код двоичного дерева, потому что я написал несколько подходов, но все они не проходят какой-либо тестовый пример.

Двоичное дерево — это специализированная версия общего дерева ^[1], поэтому любой алгоритм только для чтения, который работает с общим деревом, будет работать и с двоичным деревом.

Поскольку нахождение диаметра доступно только для чтения, алгоритм должен работать практически без изменений.

Единственное отличие состоит в том, что общее дерево имеет список дочерних элементов, в то время как двоичное дерево имеет всего 2 отдельные дочерние ссылки, но это незначительная деталь, к которой код должен легко адаптироваться.

Вы могли бы, например, улучшить 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.children на node.getChildren() в коде, и все готово.

^{Ссылка 1: разница между общим деревом и двоичным деревом}