leetcode Populating Next Right Pointers in Each Node

그림을 보면 무슨 일을 하고 싶은지 알 수 있다.
Given a binary tree

    struct TreeLinkNode {

      TreeLinkNode *left;

      TreeLinkNode *right;

      TreeLinkNode *next;

    }

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

처음에 모든 next는 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).

상수 추가 공간이 필요합니다.
 
하나의 귀속은 완성된다. 바로 귀속은 모든 노드에 그의 좌우 트리를next로 연결시키고 마지막 층까지 연결한 다음에 좌우 노드에 귀속시켜 그들의 좌우 트리를next로 연결시키는 것이다.

/**

 * Definition for binary tree with next pointer.

 * struct TreeLinkNode {

 *  int val;

 *  TreeLinkNode *left, *right, *next;

 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 * };

 */

class Solution {

public:



// left right next right left

void lr2rl(TreeLinkNode *root)

{

    if (!root) return;

    TreeLinkNode *lr = root -> left, *rl = root -> right;

    

    while(lr && rl)

    {

        lr -> next = rl;

        lr = lr -> right;

        rl = rl -> left;

    }

    lr2rl(root -> left);

    lr2rl(root -> right);

}

    void connect(TreeLinkNode *root) 

    {

        lr2rl(root);

    }

};

레이어당 완료할 수도 있습니다.

/**

 * Definition for binary tree with next pointer.

 * struct TreeLinkNode {

 *  int val;

 *  TreeLinkNode *left, *right, *next;

 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 * };

 */

class Solution {

public:

    void connect(TreeLinkNode *root) 

    {

        if (!root) return ;

        TreeLinkNode *lf = root;

        while (root)

        {

            if (root -> left)

                root -> left -> next = root -> right;

            if (root -> next && root -> next -> left)

                root -> right -> next = root -> next -> left;

            root = root -> next;

        }

        connect(lf -> left);

        connect(lf -> right);

    }

};

모든 줄을queue로 삼아 맨 왼쪽부터 맨 오른쪽까지 처리할 수 있습니다.다음 층의 맨 왼쪽을 기록하세요.계속null까지

/**

 * Definition for binary tree with next pointer.

 * struct TreeLinkNode {

 *  int val;

 *  TreeLinkNode *left, *right, *next;

 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}

 * };

 */

class Solution {

public:

    // ， queue

    void connect(TreeLinkNode *root) 

    {

        if (!root) return ;

        TreeLinkNode *lf;

        while(root)

        {

            lf = root -> left;

            while(root)

            {

                if (lf)

                    root -> left -> next = root -> right;

                if (root -> next && root -> next -> left)

                    root -> right -> next = root -> next -> left;

                root = root -> next;

            }

            root = lf;

        }

    }

};