【leetcode】Populating Next Right Pointers in Each Node I & II(middle)

Given a binary tree

    struct TreeLinkNode {

      TreeLinkNode *left;

      TreeLinkNode *right;

      TreeLinkNode *next;

    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to  NULL .
Initially, all next pointers are set to  NULL .
Note:

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,Given the following perfect binary tree,

         1

       /  \

      2    3

     / \  / \

    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \  / \

    4->5->6->7 -> NULL

 
사고방식: 한 겹 한 겹의 연결, 같은 아버지 노드의 왼쪽 나무의 이웃은 아버지 노드의 오른쪽 나무 아버지 노드의 오른쪽 나무 이웃은 아버지 노드의 왼쪽 나무
내가 쓰는 것은 차례로 돌아간다

void connect(TreeLinkNode *root) {

        if(root == NULL) return;

        TreeLinkNode * parent = root;

        TreeLinkNode * cur = parent->left;

        while(parent != NULL && cur != NULL)

        {

            cur = cur->next = parent->right; // parent 

            cur->next = (parent->next == NULL) ? NULL : parent->next->left; //   parent 

            parent = parent->next;

            cur = (parent == NULL) ? NULL : parent->left;

        }

        connect(root->left); // 

    }

대신의 비귀속 코드: 밖에 한 바퀴 대층 순환

void connect(TreeLinkNode *root) {

    if(!root)

        return;

    while(root -> left)

    {

        TreeLinkNode *p = root;

        while(p)

        {

            p -> left -> next = p -> right;

            if(p -> next)

                p -> right -> next = p -> next -> left;

            p = p -> next;

        }

        root = root -> left;

    }

}

 
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

You may only use constant extra space.

 
For example,Given the following binary tree,

         1

       /  \

      2    3

     / \    \

    4   5    7

 
After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \    \

    4-> 5 -> 7 -> NULL

 
사고방식: 비완전 두 갈래 나무.관건은 각 층이 이웃이 어느 층인지 판단하고 각 층의 첫 번째 숫자가 있는 위치도 포지셔닝해야 한다는 것이다.
나의 코드는 이전 문제의 사고방식에 따라 비귀속적이다.부모 노드에 대해 좌우 트리가 비어 있고 왼쪽 트리가 비어 있으며 오른쪽 트리가 비어 있으며 모두 비비어 분류 처리됩니다.

void connect2(TreeLinkNode *root) {

        if(root == NULL) return;

        TreeLinkNode * newroot = root;

        while(newroot != NULL) // 

        {

            TreeLinkNode * p = newroot; // 

            TreeLinkNode * cur = NULL; // 

            newroot = NULL; // 

            while(p != NULL)

            {

                if(p->left == NULL && p->right == NULL);

                else if(p->left == NULL)

                {

                    if(cur == NULL)

                        newroot = cur = p->right;

                    else

                        cur = cur->next = p->right;

                }

                else if(p->right == NULL)

                {

                    if(cur == NULL)

                        newroot = cur = p->left;

                    else

                        cur = cur->next = p->left;

                }

                else

                {

                    if(cur == NULL)

                        newroot = cur = p->left;

                    else

                        cur = cur->next = p->left;



                    cur = cur->next = p->right;

                }

                p = p->next;

            }

        }

    }

 
대신의 코드는 처리할 때 왼쪽 나무가 비어 있는지, 오른쪽 나무가 비어 있는지 나누면 된다.그렇게 많은 상황을 나눌 필요가 없다.

public class Solution {

    public void connect(TreeLinkNode root) {



        while(root != null){

            TreeLinkNode tempChild = new TreeLinkNode(0); // ， 

            TreeLinkNode currentChild = tempChild; // ， ， 

            while(root!=null){ // 

                if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;}

                if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;}

                root = root.next;

            }

            root = tempChild.next;

        }

    }

}