LeetCode OJ:Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node

 
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

알고리즘 사상: 층차적으로 훑어보는 사상에 따라 각 층의 원소를 연결하고curLev 변수로 현재 층에 접근한 몇 번째 원소를 표시하며,nextLev는 다음 층의 몇 개의 원소를 표시하고 보조 구조체 지침으로 이 층의 노드를 연결한다.여기에 임의의 두 갈래 나무의 상황을 고려하여 Populating Next Right Pointers in Each Node II도 이 답을 사용할 수 있다

/**
 * 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;
        queue<TreeLinkNode *>que;
        TreeLinkNode *p;
        p=NULL;
        int minLen=0;
		int curLev=1;
		int nextLev=0;
        que.push(root);
        while(!que.empty()){
            TreeLinkNode *cur=que.front();
            que.pop();
            if(p==NULL)p=cur;
            else {p->next=cur;p=cur;}
            if(cur->left){que.push(cur->left);nextLev++;}
            if(cur->right){que.push(cur->right);nextLev++;}
            if(--curLev==0){
				p->next=NULL;
                p=NULL;
				curLev=nextLev;
				nextLev=0;
			}
        }
    }
};

귀속판

/**
 * 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) {
        connect(root,NULL);
    }
    void connect(TreeLinkNode *root,TreeLinkNode *sibing){
        if(!root)return;
        else root->next=sibing;
        
        connect(root->left,root->right);
        if(sibing)
            connect(root->right,sibing->left);
        else 
            connect(root->right,NULL);
    }
};