1530 Number of Good Leaf Nodes Pairs

1530. Number of Good Leaf Nodes Pairs / c++ / Medium / 1시간

문제 및 코드

문제 링크

문제 코드

class Solution {
    void InitNodes(TreeNode* current, string& path)
    {
        if (current->left == nullptr && current->right == nullptr)
        {
            paths[leaves.size()] = path;
            leaves.push_back(current);
            return;
        }

        if (current->left != nullptr)
        {
            path.push_back('L');
            InitNodes(current->left, path);
            path.pop_back();
        }
        if (current->right != nullptr)
        {
            path.push_back('R');
            InitNodes(current->right, path);
            path.pop_back();
        }
    }
public:
    int countPairs(TreeNode* root, int distance) {
        int goodNodesPairCount = 0;
        leaves.clear();
        paths = vector<string>(1'025);
        // 인덱싱 후 리프 노드 담기
        string path = "";
        InitNodes(root, path);
        // 리프 노드 순회 후 거리 계산
        for (int i = 0; i < leaves.size(); ++i)
        {
            for (int j = i + 1; j < leaves.size(); ++j)
            {
                int pos = 0;
                string& path1 = paths[i];
                string& path2 = paths[j];
                while (true)
                {
                    if (path1[pos] == path2[pos])
                    {
                        pos++;
                    }
                    else
                    {
                        pos--;
                        break;
                    }
                }
                int currentDist = path1.length() + path2.length() - ((pos + 1) * 2);
                // 계산된 거리가 distance 보다 작으면 goodNodesPairCount 증가
                if (currentDist <= distance) goodNodesPairCount++;
            }
        }
        

        return goodNodesPairCount;
    }
};

접근 방식

자료구조 / 트리

1. 주어진 이진 트리에서, 임의의 두 리프 노드의 거리가 distance 이하인 노드 쌍의 수를 반환하는 문제
2. 저번에 두 노드의 거리를 구할 때, 루트 노드로부터 각 노드까지의 경로를 구한 후, 중복되는 경로를 지운 두 경로를 더하여 그 길이가 거리라는 것을 생각해냈다.
3. 우선 모든 노드를 순회하며 리프 노드를 찾고, 그 경로를 저장해줬다. (전위 순회를 하며, 백트래킹을 통해 경로를 구했다.)
4. 그 다음 i,j 로 리프 노드들을 이중 순회하여 두 리프 노드를 뽑은 뒤, 2번에 적힌 것 처럼 두 노드 사이의 길이를 구해줬다.
5. 그 길이가 distance 이하라면 goodNodesPairCount 증가 (시작값 0)
6. 순회가 끝난 후 goodNodesPairCount 반환
7. 해결

생각해 볼 점

1. 의사 코드로 먼저 생각을 정리한 뒤 문제를 푸니 훨씬 수월했다.
2. 이전에는 경로의 뒤에 ‘L’이나 ‘R’을 추가하는 식으로 풀었었는데, 백트래킹을 활용해서 경로를 추가/제거 해주니, 뒤집히지 않은 경로를 구할 수 있었다! (새로운 방법을 생각해 내서 뿌듯했다.)
3. 값이 unique(distinct) 하다는 얘기가 없었는데, 당연히 그럴 줄 알고, node->val 을 인덱스 값으로 썼더니, 문제가 발생했었다. 항상 문제를 주의 깊게 읽고, 없는 조건을 함부로 생각하지 말아야겠다.