-
[LeetCode] 116. Populating Next Right Pointers in Each Node c++Coding Test/LeetCode 2023. 1. 2. 23:12728x90
문제
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:
next pointer 를 next right node를 가르키도록 다음 포인터를 채웁니다.
next right node가 없으면 null pointer로 설정합니다.
문제 해결
Node* connect(Node* root) { //base case if (root == NULL) return NULL; //connects the left subtree of same level with right subtree of that same level if (root->left != NULL) { root->left->next = root->right; } //connect the rightmost node of a level to the leftmost node of the next level. if (root->right != NULL && root->next != NULL) { root->right->next = root->next->left; } //recursive calls for left and right subtrees. connect(root->left); connect(root->right); return root; }
다른 풀이
class Solution { public: Node* connect(Node* root) { Node *prev = root, * curr; while(prev){ curr = prev; while(curr && curr->left){ curr->left->next = curr->right; if(curr->next){ curr->right->next = curr->next->left; } curr = curr->next; } prev = prev->left; } return root; } };
728x90'Coding Test > LeetCode' 카테고리의 다른 글
[LeetCode] 994. Rotting Oranges c++ (0) 2023.01.04 [LeetCode] 542. 01 Matrix c++ (0) 2023.01.03 [LeetCode] 695. Max Area of Island c++ (0) 2022.12.28 [LeetCode] 733. Flood Fill c++ (0) 2022.12.28 [LeetCode] 1876. Substrings of Size Three with Distinct Characters c++ (0) 2022.12.27