Leetcode | Populating Next Right Pointers in Each Node I & II

Populating Next Right Pointers in Each Node I

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 7After calling your function, the tree should look like: 1 -> NULL/\2 -> 3 -> NULL/\/\4->5->6->7 -> NULL

Method I

여기에서 나는 bfs의 방법을 사용하거나 차원을 두루 훑어보라고 한다.

 1 class Solution {

 2 public:

 3     void connect(TreeLinkNode *root) {

 4         if (root == NULL) {

 5             return;

 6         }

 7         queue<TreeLinkNode*> q;

 8         TreeLinkNode* p, *endOfLayer;

 9         q.push(root);

10         endOfLayer = root;

11         

12         while (!q.empty()) {

13             p = q.front();

14             q.pop();

15             

16             if (p->left) q.push(p->left);

17             if (p->right) q.push(p->right);

18             if (p == endOfLayer) {

19                 p->next = NULL; 

20                 endOfLayer = q.back();

21             } else {

22                 p->next = q.front();

23             }

24         }

25     }

26 };

Method II

인터넷의 또 다른 방법은next라는 바늘을 이용한 것이다.k층에 접근할 때 k+1층의next 바늘을 설정합니다.각 층의 시작은front 바늘로 표시하고, 현재 층의 현재 결점은cur로 표시하며, 다음 층의 선행 결점은next로 표시합니다.넥스트가 비어 있을 때 다음 층의 첫 번째 결점임을 표시하고 특수 처리해야 합니다. 
pefect binary tree이기 때문에 다음 층으로 들어가면front=front->left;
이런 방법의 장점은 여전히 차원이 두루 흐르는 사상이지만queue, O(1)의 공간을 사용하지 않았다는 것이다.

 1 class Solution {

 2 public:

 3     void connect(TreeLinkNode *root) {

 4         if (root == NULL) {

 5             return;

 6         }

 7         

 8         TreeLinkNode *cur, *front, *next;

 9         front = cur = root;

10         next = NULL;

11         

12         while (front != NULL) {

13             if (cur->left != NULL) {

14                 if (next == NULL) {

15                     next = cur->left;

16                 } else {

17                     next->next = cur->left;

18                     next = next->next;

19                 }

20             }

21             if (cur->right != NULL) {

22                 if (next == NULL) {

23                     next = cur->right;

24                 } else {

25                     next->next = cur->right;

26                     next = next->next;

27                 }

28             }

29             cur = cur->next;

30             if (cur == NULL) {

31                 front = front->left;

32                 cur = front;

33                 next = NULL;

34             }

35         }

36     }

37 };

Method III

물론 귀속으로도 가능하다.직관적이기도 하고.

class Solution {

public:

    void connect(TreeLinkNode *root) {

        if (root == NULL) {

            return;

        }

        

        if (root->left) {

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

        }

        if (root->right && root->next) {

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

        }

        connect(root->left);

        connect(root->right);

    }

};

Populating Next Right Pointers in Each Node II

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.
O (1) 공간을 요구하는 이상queue (Method I) 와 귀환 (Method III) 을 사용하면 안 된다.
여기는 임의의binarytree이기 때문에 다음 층의 헤더 바늘을 유지해야 합니다.cur가 비어 있을 때 다음 층의 헤더 포인터를 가리키며 비어 있으면 종료합니다.그래서 순환 조건은cur!=NULL.

 1 class Solution {

 2 public:

 3     void connect(TreeLinkNode *root) {

 4         if (root == NULL) {

 5             return;

 6         }

 7         

 8         TreeLinkNode *cur, *nextFront, *next;

 9         cur = root;

10         nextFront = next = NULL;

11         

12         while (cur != NULL) {

13             if (cur->left != NULL) {

14                 if (next == NULL) {

15                     nextFront = next = cur->left;

16                 } else {

17                     next->next = cur->left;

18                     next = next->next;

19                 }

20             }

21             if (cur->right != NULL) {

22                 if (next == NULL) {

23                     nextFront = next = cur->right;

24                 } else {

25                     next->next = cur->right;

26                     next = next->next;

27                 }

28             }

29             cur = cur->next;

30             if (cur == NULL) {

31                 cur = nextFront;

32                 nextFront = next = NULL;

33             }

34         }

35     }

36 };

세 번째 브러시를 할 때 코드가 많이 간결해졌다.

 1 void connect(TreeLinkNode *root) {

 2         TreeLinkNode h(0), *p = root, *next;

 3         

 4         while (p) {

 5             next = &h;

 6             h.next = NULL;

 7             for (; p; p = p->next) {

 8                 if (p->left) {

 9                     next->next = p->left;

10                     next = next->next;

11                 } 

12                 if (p->right) {

13                     next->next = p->right;

14                     next = next->next;

15                 }

16             }

17             p = h.next;

18         }

19     }

I와 II의 코드는 일치한다.