輸出後訂單二叉搜索樹，從給定預購輸入無需構建樹或使用遞歸

鑑於代表二進制搜索樹的前序遍歷的輸入陣列，輸出一個BST的後序遍歷。

陷阱：

我已經嘗試了幾個小時，但仍然沒有線索。
最難的部分是沒有使用樹節點結構。
任何人有想法嗎？

2014-05-09 Jeff_Storm

這裏是一個暗示：

在preorder遍歷，所述陣列的所述第一單元總是將成爲根樹的，
所以如果，NodeElemnts[]給出陣列，然後NodeElemnts[0]將被樹木

然後，左節點位於2n+1和右節點位於2n+2，n的根是當前數組的索引。

的前到後：

[root][leftChild][rightChild]（前） - >[leftChild][rightChild][root]（後）.....認爲BFS :)

2014-05-09 06:23:59 NoobEditor

謝謝你的建議！問題是BST不是滿樹，節點可能有或沒有左/右孩子。 –

在這種情況下，你不會有方法來找出哪個樹節點有哪個樹孩子...假設將是樹是滿樹！ :) – NoobEditor

BST很少是一棵完整的樹，除非它是AVL樹或紅黑樹。如果樹有左孩子並且右孩子是比節點大的第一個數字，則可以找到孩子，因爲左孩子是n + 1。 –

回答