Ежедневная Проблема с кодированием Java # 008

Ежедневные проблемы с кодированием на Java (Серия из 8 частей)

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

Проблема

Универсальное дерево (что означает “универсальная ценность”) – это дерево, в котором все узлы под ним имеют одинаковое значение.

Учитывая корень двоичного дерева, подсчитайте количество одинарных поддеревьев.

Например, в следующем дереве есть 5 одномерных поддеревьев:

Стратегия

Спойлеры! Не смотрите ниже, если не хотите увидеть мое решение!

Жаргон: двоичное дерево – это древовидная структура данных, состоящая из узлов, где каждый узел может иметь 0, 1 или 2 дочерних узлов. Дочерние узлы соединены со своими родительскими узлами ребрами. Дочерний узел всегда имеет только один родительский узел. При обходе дерева, перемещаясь по его краям, родительский узел всегда ближе к корневому узлу , чем его дочерние узлы (на 1 ребро).

Если родительский узел имеет два дочерних узла, они упорядочиваются и называются левым дочерним и правым дочерним . Дочерние элементы узла и его дочерние элементы и т. Д. Являются потомками этого узла , В то время как его родитель и родитель его родителя и т. Д. Являются предками этого узла .

Левый и правый узлы могут называться родственными узлами. Узлы, не имеющие потомков, являются листьями . Узлы без родителей являются корневыми узлами (или, реже, сиротские узлы ). Поддерево – это часть большего двоичного дерева, которое содержит определенный узел исходного дерева и все потомки этого узла. Обратите внимание, что поддерево само по себе является двоичным деревом, поэтому к нему также можно применить всю вышеприведенную номенклатуру.

В постановке задачи говорится, что примерное дерево имеет пять одномерных поддеревьев. Так что это должно быть подсчет листьев (узлы без дочерних элементов) в виде одинарных поддеревьев. Тогда первое, что мы можем сделать, – это просто определить количество листьев на дереве. Количество листьев накладывает нижнюю границу на количество одновалентных поддеревьев.

Следующее, что нам нужно сделать, это посмотреть на узлы, которые не являются листьями, и пометить их Целое число unival = <0 или 1> если они являются корневым узлом поддеревьев unival и -1 в противном случае. Нам нужны четыре состояния – (1) неопределенный статус унивала, (2) определенный и 0-унивал, (3) определенный и 1-унивал, (4) определенный и не унивал.

Итак, мы начнем с построения двоичного дерева, в котором каждый узел имеет свойство unival и инициализируйте все узлы в unival (неопределенный статус). Затем мы можем написать цикл, который начинается с корневого узла дерева и делает что-то вроде:

Проверьте, является ли this.unival |/нулевым для этого узла. Если
1. this.unival равно null для этого узла, мы еще не определили статус unival поддерева этого узла; перейдите к (2). Если
2. этот.unival не является нулевым для этого узла, попытайтесь перейти к родительскому узлу этого узла. Если у этого узла есть родитель, переориентируйтесь на родительский узел, затем перейдите к началу шага (1).
  1. Если у этого узла нет родителя, мы закончили! Если у этого узла нет родителя, то он является корневым узлом всего двоичного дерева. Если мы знаем его унивальный статус, то мы должны знать унивальный статус каждого из его узлов-потомков.
  2. Чтобы проверить, является ли поддерево одномерным, мы должны проверить статус одномерности дочерних элементов его корневого узла (которых может быть 0, 1 или 2 в двоичном дереве.
Если у этого узла 0 дочерних элементов, это поддерево является одномерным. Установить
1. this.unival= значение этого узла и перейдите к (1b). Если у этого узла есть 1 дочерний узел, проверьте статус unival этого дочернего узла
2. Если статус unival ребенка не равен
  - null , установите статус unival родителя, изучив его значение и значение его ребенка, затем перейдите к шагу (1b) Если статус unival дочернего узла равен
  - null , переориентируйтесь на этот дочерний узел, затем перейдите к шагу (1 a). Если корневой узел этого поддерева имеет 2 дочерних узла, проверьте статус unival левого дочернего узла
3. Если унивальный статус левого узла не равен
  - null , проверьте унивальный статус правого узла Если унивальный статус правого узла не равен
    - null , мы можем определить статус unival его родителя по статусу этих двух узлов. Установите его, затем перейдите к шагу (1b). Если унивальный статус правого узла равен
    - null , переориентируйтесь на этот узел, затем перейдите к шагу (1 а). Если статус unival левого узла равен
  - null , переориентируйтесь на этот узел, затем перейдите к шагу (1 a).

Итак, мы начинаем с корневого узла дерева и продвигаемся вниз по левой стороне дерева, пока не дойдем до листа. Затем мы “заполняем” дерево слева направо, снизу вверх, пока не вернемся к корневому узлу. На этом этапе у нас есть все статусы unival , установленные либо -1 , 0 , или 1 , и мы можем просто посчитать количество unival > -1 узлов, чтобы получить общее количество поддеревьев unival в дереве.

Код

Прежде чем мы что-либо сделаем с поддеревьями unival, нам понадобится структура данных двоичного дерева. Нетрудно закодировать один из них с нуля, так что давайте сделаем это. Во-первых, у нас есть общий класс BinaryNode (с использованием шаблона Builder ):

package DCP;

public class BinaryNode {

  public static class Builder {

    private Integer    value  = null;
    private BinaryNode left   = null;
    private BinaryNode right  = null;

    private BinaryNode parent         = null;
    private Boolean    parentHasLeft  = null;
    private Boolean    parentHasRight = null;

    public Builder (Integer value) {
      this.value = value;
    }

    public Builder left (BinaryNode left) {

      if (left.parent() != null)
        throw new IllegalStateException(
          "ERROR: left node already has a parent");

      this.left = left;
      return this;
    }

    public Builder right (BinaryNode right) {

      if (right.parent() != null)
        throw new IllegalStateException(
          "ERROR: right node already has a parent");

      this.right = right;
      return this;
    }

    public Builder parent (BinaryNode parent) {

      if (parent == null) return this;

      this.parentHasLeft  = (parent.left()  != null);
      this.parentHasRight = (parent.right() != null);

      if (this.parentHasLeft && this.parentHasRight)
        throw new IllegalStateException(
          "ERROR: parent already has two children");

      this.parent = parent;
      return this;
    }

    public BinaryNode build() {

      BinaryNode node = new BinaryNode(this.value);

      node.left   = this.left;
      node.right  = this.right;
      node.parent = this.parent;

      if (this.left  != null) this.left.parent(node);
      if (this.right != null) this.right.parent(node);

      if (this.parent != null) {
        if (this.parentHasLeft) this.parent.right(node);
        else                    this.parent.left(node);
      }

      return node;
    }
  }

  private Integer    value    = null;
  private BinaryNode parent   = null;
  private BinaryNode left     = null;
  private BinaryNode right    = null;

  private BinaryNode (Integer value) {
    if (value < 0 || value > 1)
      throw new IllegalArgumentException(
        "this is a binary tree... `value` can only be 0 or 1");
    this.value = value;
  }

  public Integer value() {
    return this.value;
  }

  public BinaryNode parent() {
    return this.parent;
  }

  private void parent (BinaryNode parent) {
    this.parent = parent;
  }

  public BinaryNode left() {
    return this.left;
  }

  private void left (BinaryNode left) {
    this.left = left;
  }

  public BinaryNode right() {
    return this.right;
  }

  private void right (BinaryNode right) {
    this.right = right;
  }

…затем нам просто нужно добавить несколько битов и фрагментов, чтобы получить и установить статус unival узла:

...
  private Integer    unival   = null;
...
  public Integer unival() {
    return this.unival;
  }

  public void unival (Integer unival) {
    this.unival = unival;
  }
...

Я также добавил хороший (но не строго необходимый) метод для печати ASCII-представления дерева (значений или одномерных статусов):

  public void valueTree() { tree(false, 10, 10, "", false); }

  public void univalTree() { tree(true, 10, 10, "", false); }

  // some code here based on http://bit.ly/2HgFBRo
  private void tree (boolean unival, int nLevelsUp, int nLevelsDown, String indent, boolean isTail) {

    // start with any node on the tree
    BinaryNode node = this;

    // find eldest allowed node using nLevelsUp
    for (int ii = 0; ii < nLevelsUp; ++ii) {
      if (node.parent != null) {
        node = node.parent;
        ++nLevelsDown;
      } else {
        --nLevelsUp;
      }
    }

    // get number of ancestors of this node
    BinaryNode ptr = this;
    int gen = 0;

    while (ptr.parent() != null) {
      ++gen; ptr = ptr.parent();
    }

    Integer treeValue = unival ? node.unival : node.value;
    String treeLabel = (treeValue == null ? "null" : treeValue.toString());

    System.out.printf("  %3d %s|-- %s%n", gen, indent, treeLabel);

    int nChildren = (this.left == null ? 0 : 1) + (this.right == null ? 0 : 1);
    BinaryNode lastChild = (nChildren > 1 ? this.right : this.left);

    if (nLevelsDown > 0) {
      if (nChildren > 1)
        this.left.tree(unival, 0, nLevelsDown-1, indent + (isTail ? "    " : "|   "), false);

      if (nChildren > 0)
        lastChild.tree(unival, 0, nLevelsDown-1, indent + (isTail ? "    " : "|   "), true);
    }

    return;
  }

Таким образом, мы можем создавать узлы с 0, 1 или 2 дочерними элементами. Вот пример того, как мы могли бы создать небольшое двоичное дерево и проверить его свойства:

$ jshell -cp target/008-1.0-SNAPSHOT.jar 
|  Welcome to JShell -- Version 11.0.2
|  For an introduction type: /help intro

jshell> import DCP.BinaryNode

jshell> (new BinaryNode.Builder(1)).build()
$2 ==> DCP.BinaryNode@210366b4

jshell> (new BinaryNode.Builder(0).parent($2)).build()
$3 ==> DCP.BinaryNode@2b2948e2

jshell> (new BinaryNode.Builder(1).parent($2)).build()
$4 ==> DCP.BinaryNode@57536d79

jshell> (new BinaryNode.Builder(1).parent($4)).build()
$5 ==> DCP.BinaryNode@5a8e6209

jshell> $2.valueTree()
    0 |-- 1
    1 |   |-- 0
    1 |   |-- 1
    2 |       |-- 1

Отлично! Теперь нам просто нужно подумать о том, как мы будем использовать эти методы в контексте проблемы. Давайте воспользуемся процедурой, которую мы определили выше, и заменим действия фрагментами кода. Ниже это ссылка на узел, на котором мы в настоящее время сосредоточены, который меняется на протяжении всего процесса. Когда я говорю “переориентироваться на узел X” ниже, я имею в виду это это теперь относится к этому узлу:

(шаг 1)
1. если (этот.unival) перейти к (2)
2. остальное.родитель()
  1. если (родитель) сосредоточьтесь на родителе и вернитесь к началу шага (1)
  2. иначе возвращайся//мы закончили!
(шаг 2)
1. если (это.слева &&это.справа) это.unival (это.значение) и перейдите к (1b)
2. иначе, если (это.слева ^ это. справа) перейти к тому, что не- нулевой дочерний узел, затем перейдите к началу шага (1).
3. ещё
  - если (это.слева)
    - если (это.правильно) это.унивал(...) чтобы установить статус unival этого узла на основе значений левого и правого дочерних узлов, затем перейдите к шагу (1b)
    - еще сосредоточьтесь на правом узле, затем вернитесь к началу шага (2).
  - еще сосредоточьтесь на левом узле, затем вернитесь к началу шага (2).

Работает ли это? Вот сценарий, который я написал для тестирования этого алгоритма:

// Algo.java

import DCP.BinaryNode;

BinaryNode root  = (new BinaryNode.Builder(1)).build();

BinaryNode nodeA = (new BinaryNode.Builder(0).parent(root)).build();
BinaryNode nodeB = (new BinaryNode.Builder(0).parent(nodeA)).build();
BinaryNode nodeC = (new BinaryNode.Builder(1).parent(nodeA)).build();
BinaryNode nodeD = (new BinaryNode.Builder(1).parent(root)).build();
BinaryNode nodeE = (new BinaryNode.Builder(1).parent(nodeD)).build();
BinaryNode nodeF = (new BinaryNode.Builder(1).parent(nodeD)).build();

root.valueTree();

BinaryNode thisnode = root;

while (true) {

  // (1a)
  if (thisnode.unival() == null) {

    // (2a)
    if (thisnode.left() == null && thisnode.right() == null) {
      thisnode.unival(thisnode.value());

    // (2b)
    } else if (thisnode.left() != null ^ thisnode.right() != null) {
      thisnode = (thisnode.left() == null ? thisnode.right() : thisnode.left());

    // (2c)
    } else {
      if (thisnode.left() != null) {

        if (thisnode.right() != null)
          thisnode.unival((
            thisnode.left().value() == thisnode.right().value()
              ? thisnode.left().value()
              : -1
          ));

        else thisnode = thisnode.right();

      } else thisnode = thisnode.left();
    }

  // (1b)
  } else {
    BinaryNode parent = thisnode.parent();

    // (1bi)
    if (parent != null) thisnode = parent;
    else break;
  }

}

System.out.println();
root.univalTree();

……давайте попробуем это в оболочке :

$ jshell -cp target/008-1.0-SNAPSHOT.jar 
|  Welcome to JShell -- Version 11.0.2
|  For an introduction type: /help intro

jshell> /open Algo.java
    0 |-- 1
    1 |   |-- 0
    2 |   |   |-- 0
    2 |   |   |-- 0
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

    0 |-- -1
    1 |   |-- null
    2 |   |   |-- null
    2 |   |   |-- null
    1 |   |-- null
    2 |       |-- null
    2 |       |-- null

Не совсем так! Почему это произошло?

Проблема заключается в шаге (2c) алгоритма, который мы определили, или в строках:

...
      if (thisnode.left() != null) {

        if (thisnode.right() != null)
          thisnode.unival((
            thisnode.left().value() == thisnode.right().value()
              ? thisnode.left().value()
              : -1
          ));
...

Этот код проверяет, что этот узел имеет не- нулевой левый и правый дочерние элементы, но не проверяет, определен ли статус unival этих узлов! В результате мы определяем, что у корневого узла есть два дочерних узла, а затем устанавливаем статус unival корневого узла, а затем завершаем работу, не обновляя статус unival других узлов.

Это быстрое решение, все, что нам нужно сделать, это изменить приведенные выше строки на:

...
      if (thisnode.left() != null && thisnode.left().unival() != null) {

        if (thisnode.right() != null && thisnode.right().unival() != null)
          thisnode.unival((
            thisnode.left().value() == thisnode.right().value()
              ? thisnode.left().value()
              : -1
          ));
...

Давайте попробуем еще раз!

jshell> /open Algo.java
    0 |-- 1
    1 |   |-- 0
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

    0 |-- -1
    1 |   |-- -1
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

Хорошо выглядишь! Давайте попробуем другое дерево:

jshell> /open Algo.java
    0 |-- 1
    1 |   |-- 0
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 0

    0 |-- -1
    1 |   |-- -1
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- -1
    2 |       |-- 1
    2 |       |-- 0

Кажется, он ведет себя правильно. Последним шагом является подсчет количества узлов в дереве с одинаковыми статусами 0 или 1 . Мы можем сделать это, пройдя по дереву и увеличив некоторый глобальный счетчик для каждого неотрицательного узла. Что-то вроде:

public int countUnivalSubtrees (BinaryNode node) {

  boolean hasLeft  = (node.left() != null);
  boolean hasRight = (node.right() != null);

  int sumLeft  = hasLeft  ? countUnivalSubtrees(node.left()) : 0;
  int sumRight = hasRight ? countUnivalSubtrees(node.right()) : 0;

  return((node.unival() >= 0 ? 1 : 0) + sumLeft + sumRight);
}

System.out.println("\nNumber of unival subtrees: " + countUnivalSubtrees(root));

Это почти работает, но не совсем. Вы понимаете, почему?

Может быть, пример поможет:

jshell> /open Algo.java
    0 |-- 0
    1 |   |-- 0
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- 0
    2 |       |-- 0
    2 |       |-- 1

    0 |-- 0
    1 |   |-- -1
    2 |   |   |-- 0
    2 |   |   |-- 1
    1 |   |-- -1
    2 |       |-- 0
    2 |       |-- 1

Number of unival subtrees: 5

Когда у узла есть два дочерних узла, и мы проверяем их статус unival, мы проверяем только то, что они равны, но не то, что они действительны:

            thisnode.left().value() == thisnode.right().value()
              ? thisnode.left().value()
              : -1

Нам нужно проверить, что они действительны (не равны -1 ):

            thisnode.left().value() == thisnode.right().value() &&
            thisnode.left().unival() >= 0
              ? thisnode.left().value()
              : -1

Работает ли это?

jshell> /open Algo.java
    0 |-- 0
    1 |   |-- 1
    2 |   |   |-- 1
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

    0 |-- 1
    1 |   |-- 1
    2 |   |   |-- 1
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

Number of unival subtrees: 7

Почти! Нам просто нужно проверить, что статус unival поддеревьев дочернего узла равен значению этого узла:

            thisnode.left().value() == thisnode.right().value() &&
            thisnode.left().unival() >= 0  &&
            thisnode.left().value() == thisnode.value()
              ? thisnode.left().value()
              : -1

Вуаля!

jshell> /open Algo.java
    0 |-- 0
    1 |   |-- 1
    2 |   |   |-- 1
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

    0 |-- -1
    1 |   |-- 1
    2 |   |   |-- 1
    2 |   |   |-- 1
    1 |   |-- 1
    2 |       |-- 1
    2 |       |-- 1

Number of unival subtrees: 6

Обсуждение

Наконец, мы можем подсчитать количество одинарных поддеревьев в данном дереве. Давайте попробуем еще раз на примере дерева, приведенного в приглашении:

jshell> /open Algo.java
    0 |-- 0
    1 |   |-- 0
    1 |   |-- 1
    2 |       |-- 0
    2 |       |-- 1
    3 |           |-- 1
    3 |           |-- 1

    0 |-- -1
    1 |   |-- 0
    1 |   |-- -1
    2 |       |-- 0
    2 |       |-- 1
    3 |           |-- 1
    3 |           |-- 1

Number of unival subtrees: 5

Выглядит хорошо! И это дает то же значение, что и в приглашении. В более ранней версии этой записи я использовал логическое значение для статуса unival , но быстро понял, что существует более двух состояний (например, unival против не unival). Это потребовало более широкого типа данных.

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

Это решение, вероятно, можно было бы немного оптимизировать , но это проблема для другого дня.

Весь код для решения моих ежедневных проблем с кодированием доступен по адресу github.com/awwsmm/daily .

Предложения? Дайте мне знать в комментариях.

Если вам понравился этот пост, пожалуйста, подумайте о том, чтобы поддержать мою работу, купив мне кофе !

Ежедневные проблемы с кодированием на Java (Серия из 8 частей)

Оригинал: “https://dev.to/awwsmm/java-daily-coding-problem-008-1dk4”

Ежедневные проблемы с кодированием на Java (Серия из 8 частей)

Проблема

Стратегия

Код

Обсуждение

Ежедневные проблемы с кодированием на Java (Серия из 8 частей)

Читайте ещё по теме: