Java Печать печатного номера BST с круглыми скобками

Question

Я хочу вернуть строку, содержащую все ключи в дереве, в порядке их хранения. Ключи в каждом поддереве должны содержаться в скобках.

        _7_
      /     \
   _3_      8
 /     \
1       6
 \     /
  2   4
       \
        5

Выход для этого BST должен быть (((()1(()2()))3((()4(()5()))6()))7(()8())), Мой код для этого:

public String printKeysInOrder() {
    if (isEmpty()) {
        return "()";
    }

    printInOrderRec(root);

    System.out.print(sb.toString());
    return sb.toString();
}

StringBuilder sb = new StringBuilder();

private String printInOrderRec(Node root) {
    if (root == null) {
        return null;
    }
    sb.append("(");
    printInOrderRec(root.left);
    sb.append("(");
    sb.append(")");

    sb.append(root.val);

    printInOrderRec(root.right);

    return null;
}

Что дает мне вывод: (((()1(()2()3((()4(()5()6()7(()8, Я работал над этим целую вечность и не могу понять, где и как добавить пропущенные скобки. Любая помощь будет оценена.

Answer 1

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

(--------------------------------7-------)
 (------------3-----------------) (--8--)
  (--1-------) (------------6--)   () ()
   () (--2--)   (--4-------) ()
       () ()     () (--5--)
                     () ()

Здесь каждая пара в скобках определяет стек вызовов. Я не пытаюсь описать каждый стек вызовов, иначе этот ответ будет произвольно длинным. Однако из рисунка мы можем найти 5 порций в каждом стеке вызовов.

1. Левый парантез
2. Левый ребенок
3. Значение
4. Правильный ребенок
5. Правый парантез

Итак, ваш printInOrderRec Метод может выглядеть так:

private void printInOrderRec(Node root) {
    sb.append("(");
    if (root != null) {
        printInOrderRec(root.left);
        sb.append(root.val);
        printInOrderRec(root.right);
    }
    sb.append(")");
}

Примечание: я сделал тип возврата void потому что в вашем коде он ничего не возвращает, кроме нуля.