檢查給定順序是否是合法的順序遍歷

Question

如果您有一個包含十個節點的二叉搜索樹，存儲整數0至9，那麼我們如何確定一個順序不能代表樹的後序遍歷？我知道根必須是序列中的最後一個，但我無法達到任何模式。僞代碼也會很棒！ （這不是作業，爲面試練習）

Answer 1

正如你所說，你知道根源是什麼。所以你知道每個子樹中的值的範圍。如果序列（不包括根）不分割成兩個序列，一個小於一個大於根，那麼它是無效的。如果是這樣，你需要遞歸檢查兩個子遍歷。如果一切正常，那麼它是有效的。