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. 左paranthesis
2. 左子
3. 價值
4. 右鍵孩子
5. 右paranthesis

所以，你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。