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--)
                     () ()

这里每对括号都定义一个 call stack 。我不想描述每个调用堆栈，否则这个答案将任意长。不过，从图中我们可以看出每个调用堆栈有 5 个部分。

1. 左括号
2. 左 child
3. 值(value)
4. 右 child
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，因为在您的代码中它只返回 null。