1110. Delete Nodes And Return Forest
문제 요약:
Input:
Input: root = [1,2,3,4,5,6,7],
to_delete = [3,5]
Output:
Output: [[1,2,null,4],[6],[7]]
하나의 Binary Tree가 주어지고 삭제할 node들의 value들이 주어진다
주어진 to_delete에 있는 value를 가진 node들을 모두 제거하고 그로부터 파생된 여러 Binary Tree들의 root들을 반환하라
문제 분석:
- 모든 node들의 value값은 unique하다
- 반환하는 root들의 순서는 상관없다
풀이 과정:
삭제한 node의 자식들이 Binary Tree의 root가 된다, 또한 처음에 주어진 root node의 경우 삭제할 대상이 아니라면 반환해야 한다
필요한 변수는 다음과 같다
- deque<TreeNode*> to_delete_node // 삭제할 value를 가진 node들
- vector<TreeNode*> result; // 반환할 값
to_delete_node에 node들을 한번에 모았다가
result에 nullptr을 제외한 to_delete_node의 자식 node들을 넣고 처음 들어온 Binary Tree의 root의 경우에는 to_delete_node에 존재하는지 여부에 따라 넣을지 말지 판단한다
각 노드들을 순회하면서 연결을 끊는 것에 리스크를 없애기 위해 DFS를 사용했다.
그 이유는 DFS는 재귀를 통해 맨 밑의 node까지 내려갔다가 올라오면서 후속 조치를 취하기 용이하기 때문이다
삭제할 대상의 node들을 모아놓은 deque<treenode*> 타입의 to_delete_nodes 인스턴스를 생성한다
deque를 사용하는 이유는 인덱스 참조와 요소를 뒤에 추가할때 O(1)의 시간복잡도로 효율적이기 때문이다
DFS를 올라오면서 to_delete_node들을 모아둠과 동시에 해당 node를 가리키고 있는 부모 node와의 연결을 끊어준다 [O(n)]
to_delete_nodes 를 순회하면서 각 요소의 자식 노드들을 result에 넣어준다 [O(m)]
시간복잡도:
[O(n + m)]
풀이 결과:
정답이다!
배운 점 및 코드:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <deque>
using namespace std;
class Solution {
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
deque<TreeNode*> to_delete_nodes;
vector<TreeNode*> result;
// 루트 노드와 삭제한 노드의 두 자식노드들이 곧 살아남은 트리의 root가 되겠다
getDelNodes(root, to_delete, to_delete_nodes);
if (searchDelNode(root->val, to_delete) == -1)
result.push_back(root);
delNodesAndGetRoots(to_delete_nodes, result);
return result;
}
private:
int getDelNodes(TreeNode *node, vector<int>& to_delete, deque<TreeNode*>& to_delete_nodes) {
int index, left, right;
if (!node)
return (-1);
index = searchDelNode(node->val, to_delete);
if (index != -1)
to_delete_nodes.push_back(node);
// 노드의 자식노드들은 다 지나왔으므로 연결을 끊음
if (getDelNodes(node->left, to_delete, to_delete_nodes) != -1)
node->left = nullptr;
if (getDelNodes(node->right, to_delete, to_delete_nodes) != -1)
node->right = nullptr;
return index;
}
// search delete node and return index of to_delete
int searchDelNode(int value, vector<int>& to_delete) {
int index = 0;
for (auto it = to_delete.begin(); it != to_delete.end(); ++it) {
if (*it == value)
{
// to_delete.erase(it);
return index;
}
index++;
}
return (-1);
}
void delNodesAndGetRoots(deque<TreeNode*> to_delete_nodes, vector<TreeNode*> &result) {
TreeNode* node;
for (int i = 0; i < to_delete_nodes.size(); ++i) {
node = to_delete_nodes[i];
if (node->left)
result.push_back(node->left);
if (node->right)
result.push_back(node->right);
delete node;
}
}
};
갑자기 궁금한게 생겼다
// search delete node and return index of to_delete
int searchDelNode(int value, vector<int>& to_delete) {
int index = 0;
for (auto it = to_delete.begin(); it != to_delete.end(); ++it) {
if (*it == value)
{
// to_delete.erase(it);
return index;
}
index++;
}
return (-1);
}여기에서
iterator를 돌면서 erase()를 해주는게 더 빠를까? 아니면 그대로 도는게 더 빠를까?
earse()는 O(n)의 시간복잡도를 가진다고 한다 (삭제하면 뒤의 요소를 당겨야하기에)
시간복잡도 계산이 잘 안되니 일단 해보자!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
#include <deque>
using namespace std;
class Solution {
public:
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
deque<TreeNode*> to_delete_nodes;
vector<TreeNode*> result;
// 루트 노드와 삭제한 노드의 두 자식노드들이 곧 살아남은 트리의 root가 되겠다
getDelNodes(root, to_delete, to_delete_nodes);
if (to_delete_nodes.front() != root)
result.push_back(root);
delNodesAndGetRoots(to_delete_nodes, result);
return result;
}
private:
int getDelNodes(TreeNode *node, vector<int>& to_delete, deque<TreeNode*>& to_delete_nodes) {
int index, left, right;
if (!node)
return (-1);
index = searchDelNode(node->val, to_delete);
if (index != -1)
to_delete_nodes.push_back(node);
// 노드의 자식노드들은 다 지나왔으므로 연결을 끊음
if (getDelNodes(node->left, to_delete, to_delete_nodes) != -1)
node->left = nullptr;
if (getDelNodes(node->right, to_delete, to_delete_nodes) != -1)
node->right = nullptr;
return index;
}
// search delete node and return index of to_delete
int searchDelNode(int value, vector<int>& to_delete) {
int index = 0;
for (auto it = to_delete.begin(); it != to_delete.end(); ++it) {
if (*it == value)
{
to_delete.erase(it);
return index;
}
index++;
}
return (-1);
}
void delNodesAndGetRoots(deque<TreeNode*> to_delete_nodes, vector<TreeNode*> &result) {
TreeNode* node;
for (int i = 0; i < to_delete_nodes.size(); ++i) {
node = to_delete_nodes[i];
if (node->left)
result.push_back(node->left);
if (node->right)
result.push_back(node->right);
delete node;
node = nullptr;
}
}
};
다른점이 없다 둘다 21ms로 똑같이 나왔다
사실 시간복잡도상 erase()를 사용한 쪽이 O(n)이 추가되었으니 더 느리지 않을까 싶다