Sho1007

MMORPG 클라이언트 개발자 지망생

1 minute read

2096. Step-By-Step Directions From a Binary Tree Node to Another / c++ / Medium / 30분

문제 및 코드

문제 링크

image

문제 코드

class Solution {
    bool FindNode(TreeNode* current, int findValue, string& path)
    {
        if (current == nullptr) return false;

        if (current->val == findValue) return true;
        else if (FindNode(current->left, findValue, path))
        {
            path.push_back('L');
            return true;
        }
        else if (FindNode(current->right, findValue, path))
        {
            path.push_back('R');
            return true;
        }

        return false;
    }
public:

    string getDirections(TreeNode* root, int startValue, int destValue) {

        // 1.두 경로를 찾는다.
            // 1. root 에서 startValue까지의 경로
        string rootToStart = "";
        FindNode(root, startValue, rootToStart);

            // 2. root 에서 destValue까지의 경로
        string rootToDest = "";
        FindNode(root, destValue, rootToDest);

        // 2. 두 경로 중 겹치는 부분을 찾아서 지운다.
        while (rootToStart.length() > 0 && rootToDest.length() > 0)
        {
            if (rootToStart.back() == rootToDest.back())
            {
                rootToStart.pop_back();
                rootToDest.pop_back();
            }
            else break;
        }

        // 3. 1-1 (시작 노드에서 공통 부모 노드까지의)경로를 U로 대체
        for (int i = 0; i < rootToStart.length(); ++i)
        {
            rootToStart[i] = 'U';
        }
        // 4. 1-1과 1-2를 붙인다.
        reverse(rootToDest.begin(), rootToDest.end());
        string result = rootToStart + rootToDest;

        // 7. 6의 경로를 반환
        return result;
    }
};

접근 방식

자료구조 / 트리 / 문자열

  1. 트리의 시작 노드로부터 목적 노드까지의 최단 경로를 반환하는 문제
  2. 우선 경로는 시작 노드 -> 공통 부모 노드 -> 목적 노드 라고 가정했다.
  3. 2번을 만들기 위해서 아래의 두 경로를 구했다.
    1. 루트 노드에서 시작 노드까지의 경로
    2. 루트 노드에서 목적 노드까지의 경로
  4. 공통 부모를 알기 위해서 3-1, 3-2의 두 노드에서 겹치는 부분(루트 노드에서 공통 부모 노드까지의 경로)을 제거했다.
  5. 그 다음 3-1(공통 부모로부터 시작 노드까지의 경로)의 모든 원소를 U로 대체했다. (시작 노드에서 공통 부모 노드로의 경로이므로, 방향을 반대로 전환)
  6. 루트노드에서 특정 노드까지의 경로를 구할 때, 역순으로 구했기 때문에, 3-2를 뒤집어줬다.
  7. 5와 6의 경로를 더해서 반환.
  8. 해결

생각해 볼 점

  1. 트리 구조에서 시작 노드로부터 목적 노드까지의 최단 경로는 공통 부모 노드를 경유한다는 점은 빨리 생각해 낼 수 있었다.
  2. 루트 노드에서 특정 노드로의 경로를 구하는 부분을 고민했었는데, 일단 트리 순회가 필요하다고 생각해서 전위 순회(PreOrder-Traversal)로 구현했다.
  3. 그런데 해당 경로에 특정 노드가 존재하는지를 파악하기 위해 bool값도 반환이 필요했고, 만약 존재한다면 경로를 string으로도 기록해야했다.
  4. 그래서 반환값은 bool로 두고, string을 참조로 넘겨서 만약 경로 상에 찾고자 하는 노드가 존재한다면, path에 경로를 기록하는 식으로 구현했다. (이 때 구현의 용이성을 위해 path의 뒤에 추가하고 넘겨주는 식으로 구현했는데, 이로 인해 결과값은 뒤집힌 경로가 나왔다.)
  5. 트리와 트리 순회를 다시금 되짚을 수 있는 재밌는 문제였다.

You may also enjoy