1110 Delete Nodes And Return Forest

1110. Delete Nodes And Return Forest / c++ / Medium / 27분

문제 및 코드

문제 링크

문제 코드

 vector<TreeNode*> nodes;
 vector<TreeNode*> parents;

class Solution {
    void InitNode(TreeNode* current, TreeNode* parent)
    {
        if (current == nullptr) return;

        nodes[current->val] = current;
        parents[current->val] = parent;

        InitNode(current->left, current);
        InitNode(current->right, current);
    }
    
    void DeleteNode(int deleteValue)
    {
        if (parents[deleteValue] != nullptr)
        {
            if (parents[deleteValue]->left == nodes[deleteValue])
            {
                parents[deleteValue]->left = nullptr;
            }
            else
            {
                parents[deleteValue]->right = nullptr;
            }

            parents[deleteValue] = nullptr;
        }

        if (nodes[deleteValue]->left != nullptr)
        {
            parents[nodes[deleteValue]->left->val] = nullptr;
        }
        if (nodes[deleteValue]->right != nullptr)
        {
            parents[nodes[deleteValue]->right->val] = nullptr;
        }

        delete nodes[deleteValue];
        nodes[deleteValue] = nullptr;
    }
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        vector<TreeNode*> result;
        nodes = vector<TreeNode*>(1'001, nullptr);
        parents = vector<TreeNode*>(1'001, nullptr);

        InitNode(root, nullptr);

        for (int i = 0; i < to_delete.size(); ++i)
        {
            DeleteNode(to_delete[i]);
        }

        for (int i = 1; i <= 1'000; ++i)
        {
            if (nodes[i] != nullptr && parents[i] == nullptr)
            {
                result.push_back(nodes[i]);
            }
        }

        return result;
    }
};

접근 방식

자료구조 / 트리

1. 이진 트리의 루트 노드와 지워야 할 값들의 배열이 주어질 때, 지워야 할 모든 값들을 지운 후 남은 서브 트리들의 루트 노드를 배열에 담아 반환하는 문제
2. 이전 트리문제 때부터 들었던 생각이지만, 노드가 가지는 값이 유니크하다면 nodes[i] = someNode; 이런 식으로 값으로 인덱싱 할 수 있겠다고 생각했다.
3. 그리고 이번 경우에는 노드의 삭제가 핵심이었는데, 트리의 삭제를 위해 각 노드의 부모 노드도 인덱싱했다.
   (parents[i] : i값을 가지는 노드의 부모 노드)
4. 2와 3이 준비된 이후 노드 삭제에는 아래의 단계를 따른다.
   1. 부모가 있다면, 부모의 자식 노드(지워야 할 노드)로의 연결을 끊는다.

       // 만약 지워야 할 노드가 부모의 왼쪽 자식이라면
       if (parentNode->left == currentNode)
       {
           parentNode->left = nullptr;
       }
       // 그게 아니라면 (지워야 할 노드가 부모의 오른쪽 자식이므로)
       else
       {
           parentNode->right = nullptr;
       }
              
      

   2. 현재 노드의 왼쪽 자식이 있다면, 해당 자식과 부모로의 연결을 끊는다.

       if (currentNode->left != nullptr)
       {
           // 현재 노드의 왼쪽 자식의 부모를 nullptr로 만든다.
           parents[currentNode->left->val] = nullptr;
           // 그리고 현재 노드의 왼쪽 자식을 nullptr로 만든다.
           currentNode->left = nullptr; 
       }
      

   3. 2번의 과정을 현재 노드의 오른쪽 자식에도 똑같이 해준다.
5. 그리고 모든 노드를 순회하면서 아래 조건을 만족하면, result 값을 증가시켜 준다.
   1. 현재 노드가 nullptr 이 아니고 (지워지지 않았고)
   2. 현재 노드의 부모 노드가 nullptr 이면 (부모노드가 없으면 -> 서브 트리이면)
6. result 를 반환
7. 해결

생각해 볼 점

1. 트리의 삭제를 되짚어 볼 수 있는 재밌는 문제였다.