[C++] LeetCode : Populating Next Right Pointers in Each Node

Question

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

 

완전 이진트리가 주어진다면 같은 레벨의 노드를 모두 오른쪽으로 연결하는 함수를 작성하라. 

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

 

You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

 

제약사항

• The number of nodes in the tree is in the range [0, 2^12 - 1].
• -1000 <= Node.val <= 1000

---

Solution

문제를 풀 때 고려한 사항

• 주어진 input이 비어있을 때도 정상 동작해야 한다.
• Output에 level의 변화에 따라 #을 삽입해야 하나? -> return 타입이 Node 인걸 보아 그냥 연결만 해주면 되는 것 같다. 

---

Solution

예제를 그려서 알고리즘을 구상해보자,
      1
    2   3
   4 5 6 7
완전 이진트리이기 때문에 각 트리의 Level에 해당하는 index가 고정이라고 볼 수 있다. 루트 노드의 index를 1이라 하였을 때, 

idx   1 2 3 4 5 6 7
num 1 2 3 4 5 6 7

레벨 0 : 1개 : 1
레벨 1 : 2개 : 2 ~ 3
레벨 2 : 4개 : 4 ~ 7
레벨 3 : 8개 : 8 ~ 16
...

즉, 각 레벨의 노드 개수는 2의 level승이 존재할 것이고, index 도 2의 level승부터 시작할 것이다. 

따라서 각 노드의 index를 기억해두고 순서대로 연결하면 될 것 같다. 

 

class Solution {
public:
    Node* connect(Node* root) {
    	if(root == nullptr) return nullptr;

        map<int, Node*> node_map;
        node_map[1] = root;

        for(int i=1;;i++){ // scope 설정
    		if(node_map.find(i) == node_map.end()) break;
			if(node_map[i]->left){
				node_map[i*2] = node_map[i]->left;
			}
			if(node_map[i]->right){ // 완전 이진트리이기 때문에, 올바른 입력만 주어진다면 오른쪽 노드는 검사할 필요가 없긴하다. 
				node_map[i*2+1] = node_map[i]->right; 
			}
        }

        for(int i=1, level_index=2; ;i++){
			if(node_map.find(i) == node_map.end()) break;

			if(i+1<level_index) { 
				node_map[i]->next = node_map[i+1];
			}
			if(i+1 == level_index) level_index <<= 1;
        }
      	return root;
    }
};

• Time complexity : O(N), map에 배치하는데 O(N), 연결해주는데 O(N) 으로 총 O(2N) == O(N)이다.  
• Space Complexity : O(N),  map배치를 위한 공간 O(N)이 소요된다. 

Solution2

보통 level별로 뭔가 작업을 처리해줘야 할 때 stack/queue을 많이 쓰는 것 같다. 
마찬가지로 이 문제도 stack/queue를 사용해서 해결해본다. 

두 개의 큐을 사용한다.
각 큐는 현재 level과 다음 level의 노드를 담는 역할을 한다. 

class Solution {
public:
    Node* connect(Node* root) {
    	if(root == nullptr) return nullptr;

		queue<Node*> curr_level;
		queue<Node*> next_level;

		curr_level.push(root);

		while(!curr_level.empty()){
			Node* curr = curr_level.front();
			curr_level.pop();

			if(curr->left){
				next_level.push(curr->left);
			}
			if(curr->right){
				next_level.push(curr->right);
			}

			if(curr_level.empty()){
				swap(curr_level,next_level);
			}else{
				curr->next = curr_level.front();
			}
		}

		return root;
	}
};

• Time complexity : O(N) 
• Space Complexity : O(1)

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/108/trees-and-graphs/789/

Explore - LeetCode