앞 순서와 중간 순서로 두 갈래 트리 만들기

점: 두 갈래 나무의 이해, 코드 능력
제목: 앞의 순서와 중간의 순서에 따라 대응하는 두 갈래 트리를 만듭니다.
순서: 16, 7, 6, 3, 14, 12, 8, 15, 28, 23, 27, 41, 30, 29, 55
및 중간 시퀀스: 3, 6, 7, 8, 12, 14, 15, 16, 23, 27, 28, 29, 30, 41, 55
검지offer 면접문제 6
사고방식: 1. 앞의 순서 반복 서열의 첫 번째 요소는 바로 루트 노드이다. 이것은 뒤의 순서 반복이 정돈된 것과 반대로 뒤의 순서 반복 서열은 마지막 요소는 루트 노드이다.
2. 전형적인 두 갈래 나무, 즉'왼쪽 노드는 아버지 노드보다 값이 작고 오른쪽 노드는 아버지 노드보다 값이 크다'는 두 갈래 나무는 중차 서열이 필요 없고 앞차나 뒤차로만 유일하게 두 갈래 나무를 확정할 수 있다.
3. 그러나 이런 문제에서 도출하고자 하는 두 갈래 나무는'왼쪽 노드는 아버지 노드보다 값이 작고 오른쪽 노드는 아버지 노드보다 값이 크다'는 규칙을 따르지 않아도 된다. 이때 단독의 앞 노드나 뒤 노드는 층별로 훑어보는 것을 포함하고 그 서열은 유일한 두 갈래 나무에 대응할 수 없다.반드시 중간 순서로 시퀀스를 옮겨야 한다.
원인은 매우 간단하다. 앞의 순서와 뒤의 순서가 왼쪽 작은 오른쪽의 큰 규칙을 따르지 않을 때 잎 노드가 아버지 노드의 왼쪽 아이인지 오른쪽 아이인지 확정할 수 없다.만약에 아버지 노드 A에 하위 노드 B가 있다면 왼쪽 아이가 B든 오른쪽 아이가 B든 전 서열 반복 결과는 영원히 AB이고 후 서열 반복 결과도 영원히 BA이다. 이때 전 서열 반복 서열과 후 서열 반복 서열을 동시에 정해도 도대체 B가 A의 왼쪽 노드인지 오른쪽 노드인지 알 수 없다.
그러나 앞서열이든 뒤서열이든 다시 중서열을 정한다면 B가 A의 왼쪽 노드든 오른쪽 노드든 정할 수 있다. 왜냐하면 중서 자체가 하위 노드가 아버지 노드의 왼쪽 아이든 오른쪽 아이든 정할 수 있기 때문이다.
4. 위의 1-3을 바탕으로 창설 방식은 다음과 같다. 1. 앞의 순서 반복 서열: 첫 번째는 루트 노드이고 중간 순서로 왼쪽 트리의 부분, 오른쪽 트리의 부분을 확정한다.
2. 왼쪽 나무의 첫 번째 노드, 왼쪽 나무의 뿌리 노드, 그리고 법대로 첫 번째 단계, 오른쪽 나무도 마찬가지로 이런 전형적인 사용은 귀속된다
중서의 좌우 경계 기능: 좌우 자목과 좌우 잎 노드를 효과적으로 구분하는 것이 이런 문제의 관건이다
3. 귀속 생성 노드, 귀속 종료 조건 즉 경계 조건 주의
후차 역행 서열 + 중차 역행 서열, 층차 역행 서열 + 중차 역행 서열은 모두 유사한 이치로 유일한 두 갈래 나무를 생성할 수 있다. 다른 것은 모두 안 된다. 왜냐하면 아이가 왼쪽인지 오른쪽인지 확인할 수 없기 때문이다.
코드:

#include 

template struct Node {
    T val;
    Node *lchild;
    Node *rchild;
    Node(T _val):val(_val), lchild(nullptr), rchild(nullptr) {}
};

template class Btree {
    Node *root;

public:
    Btree():root(nullptr) {}
    void Free (Node *cur) {
        if (cur) {
            Free(cur->lchild);
            Free(cur->rchild);
            delete cur;
            cur = nullptr;
        }
    }
    ~Btree () {
        Free(root);
    }

    void Add (T val) {
        if (!root) {
            root = new Node(val);
        } else {
            Node *cur = root;
            while (cur) {
                if (cur->val > val) {
                    if (cur->lchild) {
                        cur = cur->lchild;
                    } else {
                        cur->lchild = new Node(val);
                        break;
                    }
                } else if (cur->val < val) {
                    if (cur->rchild) {
                        cur = cur->rchild;
                    } else {
                        cur->rchild = new Node(val);
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }

    void Pre (Node *cur) {
        if (cur) {
            std::cout << cur->val << "\t";
            Pre(cur->lchild);
            Pre(cur->rchild);
        }
    }
    
    void pre () {
        Pre(root);
        std::cout << std::endl;
    }

    void Mid (Node *cur) {
        if (cur) {
            Mid(cur->lchild);
            std::cout << cur->val << "\t";
            Mid(cur->rchild);
        }
    }
    
    void mid () {
        Mid(root);
        std::cout << std::endl;
    }
};

void recreate (int *pre, int *mid, const int size, int prestart, int preend, int midstart, int midend, Btree &bt) {
    if (preend - prestart != midend - midstart) {
        return;
    }

    if (prestart > preend || midstart > midend || prestart >= size || preend >= size || !pre || !mid) {
        return;
    }

    std::cout << "inesrt node idx " << prestart << "(" << pre[prestart] << ")" << std::endl;
    bt.Add(pre[prestart]);
    if (prestart == preend && midstart == midend) {
        return;
    }
    
    int mididx = -1, count = 0;
    for (int i = midstart; i <= midend; i++) {
        if (pre[prestart] == mid[i]) {
            mididx = i;
            break;
        } else {
            ++count;
        }
    }

    std::cout << "left(pre; mid): " << (prestart + 1) << ", " << prestart + count << "; " << midstart << ", " << (mididx - 1) << std::endl;
    std::cout << "right(pre; mid): " << (prestart + count + 1) << ", " << preend << "; " << (mididx + 1) << ", " << midend << std::endl << "---------------------" << std::endl;
    if (mididx > 0) {
        recreate(pre, mid, size, prestart + 1, prestart + count, midstart, mididx - 1, bt);
        recreate(pre, mid, size, prestart + count + 1, preend, mididx + 1, midend, bt);
    }
}

void recreate_btree_by_pre_and_mid (int *pre, int *mid, int size) {
    Btree bt;
    recreate(pre, mid, size, 0, size - 1, 0, size - 1, bt);
    bt.pre();
    bt.mid();
}

int main () {
    int pre[] = {16, 7, 6, 3, 14, 12, 8, 15, 28, 23, 27, 41, 30, 29, 55};
    int mid[] = {3, 6, 7, 8, 12, 14, 15, 16, 23, 27, 28, 29, 30, 41, 55};
    recreate_btree_by_pre_and_mid(pre, mid, sizeof(pre)/sizeof(pre[0]));
    return 0;
}