題目描述

給定一組字串表示的整數陣列，為一棵 二元搜尋樹（BST） 的 層序遍歷結果，其中 "null" 表示對應位置上為空節點。請你根據這組輸入還原出這棵 BST，並輸出其 中序遍歷 的結果。

輸入格式

第一行一個整數 $n$，表示層序輸入的節點數量（包括 "null"）。
第二行 $n$ 個用空格分隔的字串，為節點值或 "null"。

輸出格式

輸出一行整數，為還原 BST 的中序遍歷結果，數字之間以空格分隔。

輸入範例

9
5 3 8 1 4 6 9 null null

輸出範例

1 3 4 5 6 8 9

資料範圍

• $1 \leq n \leq 10^4$
• 合法數字節點為 $1 \leq$ 節點值 $\leq 10^9$
• "null" 表示空節點，不會插入