두 갈래 나무를 나선형 순서에 따라 층으로 나누어 연결하다

Write a program to convert binary tree in to doubly linked list such that doubly linked list represents the spiral order of given tree using recursion, Inplace(no Extra Space except recursion memory stack)
given pointer to head of binary tree
1/\2 3/\/\4 5 6 7
doubly linked list represent
head-> 1 2 3 7 6 5 4
마지막 두 알고리즘은 모두 오류가 있습니다. 현재의 두 알고리즘을 기준으로 합니다.
만약 추가 공간을 사용한다면 두 번째 알고리즘도 오류입니다.vec를 넣는 순서와vec에서 읽는 순서의 주기에 문제가 있어서 나선형으로 인쇄할 수 없습니다.이렇게 할 수 있다. 각 층을 연결하기 전에 먼저 왼쪽에서 오른쪽으로 노드의 left와right를vec에 넣은 다음에 flag가 왼쪽에서 오른쪽으로 나오느냐 오른쪽에서 왼쪽으로 노드를vec에서 꺼내서 이중 체인표로 연결한다. 각 층의 flag는 반대이다.

struct node{
    int val;
    node *left;
    node *right;   
};

void append(node* &head, vector<node*>&vec, int beg, int end, bool flag ) {
    if (flag) {
        for (int i = beg; i <= end; ++i) {
            node* n = vec[i];
            n->right = NULL;
            head->right = n;
            n->left = head;
            head = n;
        }
    }
    else {
        for (int i = end; i >= beg; --i) {
            node* n = vec[i];
            n->right = NULL;
            head->right = n;
            n->left = head;
            head = n;
        }
    }
}

void push(vector<node*>& vec, int beg, int end) {
    for (int i = beg; i <= end; ++i) {
        node *n = vec[i];
        if (n->left) vec.push_back(n->left);
        if (n->right) vec.push_back(n->right);
    }
}

node* bitree2dlink(node *root) {
    if (!root) return NULL;
    vector<node*> vec;
    int beg = 0;
    int end = 0;
    vec.push_back(root);
    node head;
    head->left = NULL;
    head->right = NULL;
    node *pt = &head;
    bool flag = false;
    while(vec.size() > 0) {
        push(vec, beg, end);
        append(pt, beg, end, flag);
        flag = !flag;
        beg = end + 1;
        end = vec.size() - 1;
    }
    return pt->right;
}

만약 추가 공간을 사용하지 않고 귀속을 직접 사용하는 방법은 각 노드가 있는 층의 높이에 따라 귀속 검색을 통해 이 층의 노드를 모두 연결하는 것이다.주의해야 할 것은 고층 노드에서 하층 노드의 방향으로 갈 수 없다는 것이다. 왜냐하면 다음에 귀속할 때 반드시 고층 노드를 거쳐야 하층 노드에 도착할 수 있기 때문이다.밑바닥에서 고층으로 층층이 연결되다.level=height 때 연결된 것은 마지막 층,level=head-1, 두 번째 층,level=0, 바로 연결된 최고층의 그 노드입니다.주의해야 할 것은 노드를 양방향 체인 시계에 넣을 때 머리에서 첨가하는 것이다.

int height(node* root) {
    if (root == NULL) return 0;
    return max(height(root->left)+1, height(root->right) + 1);
}

void tree2link(node*pt, node* n, int level, bool flag) {
    if (n == NULL) return;
    if (level == 0) {
         n->right = pt->right;
         if (pt->right) pt->right->left = n;
         pt->right = n;
         n->left = pt;
    }
    if (level > 0) {
        if (flag) {
            tree2link(pt, n->left, level - 1, flag);
            tree2link(pt, n->right, level - 1, flag);
        }
        else {
            tree2link(pt, n->right, level - 1, flag);
            tree2link(pt, n->left, level - 1, flag);
        }
    }
}

node *recurBitree2dl(node *root) {
    if (!root) return NULL;
    node head;
    node* pt = &head;
    int h = height(root) - 1;
    bool flag = true;
    for (int i = h; i >= 0; --i) {
        tree2link(pt, root, i, flag);
        flag = ~flag; 
    }
}

////////////////////////////////////////////////////////////////////////////////////
다음 코드에 오류가 있습니다.
만약 추가 공간을 사용할 수 있다면, 제목은 상대적으로 비교적 간단하다

Node *tree2Link(Node *root) {
    if (root == NULL)
        return NULL;

    vector<Node *> vec;
    bool flag = true;
    vec.push_back(root);

    int beg = 0, end = 0;
    Node head;
    Node *t = &head;

    while (!vec.empty()) {
        if (flag) {
            int i = beg;
            for (;i< = end; ++i) {
                Node *tmp = vec[i];
                if (tmp->left)
                    vec.push_back(tmp->left);
                if (tmp->right)
                    vec.push_back(tmp->right);
                t->right = tmp;
                tmp->left = t;
                
                t = tmp;

            }

           
        }
        else {
            int i = end;
            for (; i >= beg; --i) {
                Node *tmp = vec[i];
                if (tmp->right)
                    vec.push_back(tmp->right);
                if (tmp->left)
                    vec.push_back(tmp->left);

                t->right = tmp;
                tmp->left = t;

                t = tmp;
            }


        }

        beg = end + 1;
        end = vec.size() - 1;

        flag = ~flag;
    }

    return head.right;

}

별도의 공간을 두지 않고 인터넷에서 한 가지 방법을 보면 복잡도가 비교적 높지만 사고방식은 괜찮다.
먼저 수의 높이를 계산하고 최저 층부터 층층이 연결한다.

struct node
{
    struct node *left;
    struct node *right;
    int data;

};

struct node *rslt;//Global structure pointer..it point to head of doubly linked list 


int height(struct node* head)
{

    if(head==NULL)
        return 0;

    if(head->left==NULL && head->right==NULL)
        return 0;

    int lh=height(head->left);
    int rh=height(head->right);

    return lh>rh?(lh+1):(rh+1);

}

struct node* appnd(struct node *a,struct node *b)
{
    if(a==NULL)return b;
    if(b==NULL)return a;

    struct node* result=a;
    while(a->left!=NULL)
        a=a->left;

    a->left=b;
    b->right=a;

    //b->left=NULL;


    return result;

}

void printGivenLevel(struct node* head,int level,int ltr)
{
    if(head==NULL)
        return;

    if(level==0)
    {
        appnd(rslt, head);
        rslt = head;
    }

    if(level>0)
    {

        if(ltr)
        {
            printGivenLevel(head->left,level-1,ltr);
            printGivenLevel(head->right,level-1,ltr);
        }
        else
        {
            printGivenLevel(head->right,level-1,ltr);
            printGivenLevel(head->left,level-1,ltr);

        }
    }

}

void printGivenOrder(struct node* head)
{

    int i=0;
    int ltr=0;

    for(i=height(head); i >= 0; i--)
    {

        printGivenLevel(head,i,ltr);
        ltr=~ltr;
    }

}

struct node* NewNode(int data)
{
    struct node* tmp=(struct node *)malloc(sizeof(struct node));
    tmp->data=data;
    tmp->left=NULL;
    tmp->right=NULL;
    return tmp;

}

void printList(struct node* node)
{
    struct node* current=node;
    while(current)
    {
        printf("%d ----> ",current->data);
        current=current->right;
    }


}

int main()
{
    struct node* start=NULL;

    start=NewNode(1);
    start->left=NewNode(2);
    start->right=NewNode(3);
    start->left->left=NewNode(4);
    start->left->right=NewNode(5);
    start->right->left=NewNode(6);
    start->right->right=NewNode(7);

    printGivenOrder(start);

    printList(rslt);

    return 0;

}