Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A binary search tree is a binary tree that satisfies the following properties:

·        The left subtree of a node contains only nodes with keys less than the node's key.

·        The right subtree of a node contains only nodes with keys greater than the node's key.

·        Both the left and right subtrees must also be binary search trees.

 

 

Figure 1. Example binary search tree

 

            Pre-order traversal (Root-Left-Right) prints out the node’s key by visiting the root node then traversing the left subtree and then traversing the right subtree. Post-order traversal (Left –Right-Root)  prints out the left subtree first and then right subtree and finally the root node. For example, the results of pre-order traversal and post-order traversal of the binary tree shown in Figure 1 are as follows:

Pre-order:       50 30 24 5 28 45 98 52 60 

Post-order:     5 28 24 45 30 60 52 98 50

 

 

Given the pre-order traversal of a binary search tree, you task is to find the post-order traversal of this tree.

 

Input

The keys of all nodes of the input binary search tree are given according to pre-order traversal. Each node has a key value which is a positive integer less than 10⁶. All values are given in separate lines (one integer per line). You can assume that a binary search tree does not contain more than 10,000 nodes and there are no duplicate nodes.

 

Output

The output contains the result of post-order traversal of the input binary tree. Print out one key per line.

 

Sample input	Sample output
50 30 24 5 28 45 98 52 60	5 28 24 45 30 60 52 98 50

 

---

作法 : 按照順序分成兩個區塊, 這就意味著我們需要找尋最鄰近且比根大的節點
例如 :
範例輸入

50 30 24 5 28 45 98 52 60 對於 50 來說, 98 是最鄰近且大於 50

則 50 [30 24 5 28 45][98 52 60] 最後輸出 50

30 [24 5 28][45] 對 30 來說 45 是最鄰近且大於 30, 最後輸出 30

...

採用了 Sparse Table 完成了 O(nlogn*logn),

避免了O(n*n)的最慘結果

#include<stdio.h>
#define L 10000
int SparseTable[L][15], A[L]; /*2^14 = 16384 >= L*/
int Max(int x, int y) {
    return x > y ? x : y;
}
int Build(int *A, int n) {
    int i, t, k;
    for(i = 0; i < n; i++)
        SparseTable[i][0] = A[i];
    for(k = 1, t = 2; t <= n; k++, t <<= 1)
        for(i = 0; i+t <= n; i++)
            SparseTable[i][k] = Max(SparseTable[i][k-1], SparseTable[i+(t>>1)][k-1]);
}
void PostOrder(int i, int n) {
    int k, t, st = i, cut;
    if(i > n)    return;
    while(1) {
        cut = -1;
        for(k = 1, t = 2; st+t <= n; k++, t <<= 1)
            if(SparseTable[st][k] > SparseTable[st][0]) {
                cut = 1;
                break;
            }
        if(SparseTable[st][0] > SparseTable[i][0])
            {cut = 0;break;}
        if(cut == -1 && st > n)    break;
        st = st + (t>>1);
    }
    
    if(cut != -1) {
        PostOrder(i+1, st-1);
        PostOrder(st, n);
    } else {
        PostOrder(i+1, n);
    }
    printf("%d\n", A[i]);
}
int main() {
    int i = 0;
    while(scanf("%d", &A[i]) == 1)
        i++;
    Build(A, i);
    PostOrder(0, i-1);
    return 0;
}