java 按带括号的 BST 顺序打印

Question

我想要 return 一个包含树中所有键的字符串，按照它们的存储顺序。每个子树中的键都应该包含在括号中。

这个 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个部分。

左括号
左孩
价值
右子
右括号

因此，您的 printInOrderRec 方法可能如下所示：

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

注意： 我已将 return 类型设置为 void 因为在您的代码中它 return 只是 null。

java 按带括号的 BST 顺序打印

java Printing inorder BST with parenthesis

java

string

parentheses

inorder

binary-search-tree