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

 

---

遞迴建樹。

#include <stdio.h>
int n, A[100005];
struct node {
    int l, r, v;
};
int size = 1, idx;
node Nd[100005];
int build(int vl, int vr, int nd) {
    Nd[nd].v = A[idx];
    idx++;
    if(idx < n && A[idx] < Nd[nd].v && A[idx] >= vl) {
        Nd[nd].l = ++size;
        build(vl, Nd[nd].v, size);
    }
    if(idx < n && A[idx] > Nd[nd].v && A[idx] <= vr) {
        Nd[nd].r = ++size;
        build(Nd[nd].v, vr, size);
    }
}
int travel(int nd) {
    if(Nd[nd].l)
        travel(Nd[nd].l);
    if(Nd[nd].r)
        travel(Nd[nd].r);
    printf("%d", Nd[nd].v);
    puts("");
}
int main() {
    n = 0, idx = 0;
    while(scanf("%d", &A[n]) == 1)
        n++;
    build(-0xfffffff, 0xfffffff, 1);
    travel(1);
    return 0;
}