[LeetCode] Populating Next Right Pointers in Each Node I, II

제목:
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

분석:
이 문제를 올린 것은 제목에 있는 그 말 때문이다: You may only use constant extra space
이것은 깊은 검색은 사용할 수 없다는 것을 의미한다. 귀속은 창고가 필요하기 때문에 공간의 복잡도는 O(logn)가 될 것이다.의심할 여지없이 검색도 사용할 수 없다. 왜냐하면 대기열도 공간을 차지하고, 공간의 점용은 O(logn)보다 높기 때문이다.
 
어려우면 여기 있을 수 없고, 깊은 수색과 광범위한 수색도 쓸 수 없는데, 어떻게 나무의 두루 다니기를 완성합니까?
내가 제목을 얻은 첫 번째 반응은 바로 광수를 사용하고, 이어서 광수를 사용할 수 없다는 것을 발견하면 어려움을 겪는다는 것이다.
몇 가지 힌트를 보았는데, 핵심은 여전히 광범위한 검색이지만, 우리는next 바늘을 빌려 대기열이 필요 없이 광범위한 검색을 완성할 수 있다.
 
현재 층의 모든 결점의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:
    void connect(TreeLinkNode *root) {
        if(NULL == root) return;
        TreeLinkNode* curLev;
        while(root -> left != NULL){
            curLev = root;
            while(curLev != NULL){
                curLev -> left -> next = curLev -> right;
                if(curLev -> next != NULL)
                    curLev -> right -> next = curLev -> next -> left;
                curLev = curLev -> 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

뒤이어 제목이 약간 바뀌었다. 꼭 두 갈래 나무가 가득한 것은 아니다.
 
해법의 핵심: 점차적인 사상은 여전히 바꿀 필요가 없고, 여전히 현재 층의 넥스트 바늘에 근거하여 다음 층의 넥스트 바늘을 설정한다.단지 결점을 찾는 것이 번거롭다. 우리는 두 가지 함수를 정의했다.findNextNodeNextLev는 (n+1)층의 다음 노드를 찾고,findStartNodeNextLev는 다음 층의 시작 노드를 찾는 데 사용한다.

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(NULL == root) return;
        TreeLinkNode* start;
        TreeLinkNode* curNode;
        TreeLinkNode* nextNode;
        while(root != NULL){
            start = findStartNodeNextLev(root);
            curNode = start;
            nextNode = findNextNodeNextLev(root, start);
            while(nextNode != NULL){
                curNode -> next = nextNode;
                curNode = nextNode;
                nextNode = findNextNodeNextLev(root, curNode);
            }
            root = start;
        }
    }
private:
    TreeLinkNode* findNextNodeNextLev(TreeLinkNode* &cur, TreeLinkNode* curNextLev){
        if(cur -> left == curNextLev && cur -> right != NULL){
            return cur -> right;
        }else{
            while(cur -> next != NULL){
                cur = cur -> next;
                if(cur -> left != NULL && cur -> left != curNextLev) return cur -> left;
                if(cur -> right != NULL && cur -> right != curNextLev) return cur -> right;
            }
        }
        return NULL;
    }
    
    TreeLinkNode* findStartNodeNextLev(TreeLinkNode* node){
        if(NULL == node) return NULL;
        if(node -> left != NULL) return node -> left;
        return findNextNodeNextLev(node, node -> left);
    }
};