Путь к двоичному дереву () Реализация - PullRequest
Новая
       13

Путь к двоичному дереву () Реализация

0 голосов
/ 17 июня 2020

Я работаю над программным заданием, которое требует, чтобы мы написали метод пути (root, значение), который возвращает LinkedList перечислений направлений (слева, справа), который ведет к целевому узлу (значению). Нам не разрешено создавать какие-либо новые поля, чтобы это произошло, поэтому я создал метод pathHelper (). Один из неудачных тестов должен возвращать: left, right в качестве пути, но он возвращает left, right, left, right . Я не уверен, почему он считает шаги дважды. Мы ценим любые предложения! ПРИМЕЧАНИЕ. Это двоичное дерево, не BST. Мы должны использовать исчерпывающий подход DFS. 

    public static <T> LinkedList<BinaryNode.Direction> path(BinaryNode<T> root, T value) {
        if (root == null) {
            return null;
        } else if (root.payload == value) {
            return new LinkedList<>();
        }
        LinkedList<BinaryNode.Direction> list = new LinkedList<>();
        pathHelper(root, value, list);
        return list;
    }

    public static <T> void pathHelper(BinaryNode<T> root, T value, LinkedList<BinaryNode.Direction> list) {
        if (root.left != null) {
            if (root.payload != value) {
                list.add(BinaryNode.Direction.left);
            }
            pathHelper(root.left, value, list);
        } if (root.right != null) {
            if (root.payload != value) {
                list.add(BinaryNode.Direction.right);
            }
            pathHelper(root.right, value, list);
        }
    }

1 Ответ

0 голосов
/ 17 июня 2020

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

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

private boolean findPath(BinaryNode<T> node, T value, List<BinaryNode.Direction> directions) {
    if (node == null) {
        return false;
    } else if (node.payload.equals(value)) {
        return true;
    } else if (findPath(node.left, value, directions)) {
        directions.add(0, BinaryNode.Direction.LEFT);
        return true;
    } else if (findPath(node.right, value, directions)) {
        directions.add(0, BinaryNode.Direction.RIGHT);
        return true;
    } else {
        return false;
    }
}

Обратите внимание, что это вставляет направление в начало списка, чтобы убедиться, что он в правильном порядке. Это также позволяет вам определить, где root имеет значение, потому что он вернет true, но путь будет пустым.

...