문제 요약:
Input:
root = [5,1,2,3,null,6,4] - 이진트리의 root node
startValue = 3 - 시작 노드의 value
destValue = 6 - 목적지 노드의 value
Output:
"UURL"
입출력의 의미는 다음과 같다
root = Binary Tree의 Root Node
startValue = 시작 Node의 value
destValue = 목적지 Mode의 value
"U" = 부모Node로 이동
"L" = 좌측 자식 Node 로 이동
"R" = 우측 자식 Node 로 이동
주어진 Binary tree에서 startValue값을 가진 Node 부터 destValue값을 가진 Node 까지 이동하는 최소한의 이동 루트를 문자열로 반환하라
문제 분석:
- 모든 노드들의 value값은 unique하다
풀이 과정:
문제의 답 패턴은 연속된 "U"가 공통 부모Node를 찾을 때 까지 추가되었다가 그 이후에 목적지Node를 찾기위해 "L", "R" 을 반복하는 구조이다
그렇기에 "U"의 개수는 곧 시작Node로부터 공통 부모Node 와의 깊이(Depth)차이가 되므로 DFS(Depth First Search)로 탐색을 진행하기로 했다
DFS를 최적화 하기위해 BackTracking기법을 사용했다
"L", "R"은 어떻게 구하는가?
그건 그냥 목적지Node의 최단 루트를 그냥 공통 부모Node 부터 루트를 시작하여 "L", "R" 값들을 알아내면 된다
DFS를 통해 얻을 내용은 다음과 같다
- 공통 부모 Node
- 각 시작, 목적지 Node의 최단 루트
각 Node를 향한 최단 루트를 통해 공통 부모Node를 찾아낼 것이다.
그렇게되면 시작Node의 depth는 최단 루트의 크기와 동일할 것이고는 "U" 의 개수를 구하는데에 사용이 될것이다
DFS 한번으로 이 둘을 구할 수 있었으나 내 능력의 한계로 가독성이 너무 안좋아져서 그냥 시작, 목적지 Node를 기준으로 두번 나눠서 탐색을 진행했다
각 Node의 최단 루트에는 pair<int, string> 형식으로 각 노드의 value와 해당 Node로 진입했을 때 왼쪽 자식으로 진입했는지 오른쪽 자식으로 진입 했는지에 대한 여부를 "L", "R" 로 구별하여 추가 했다.
이렇게 두 루트를 인덱스 참조를 통해 처음부터 비교해가며 가장 뒤쪽에 있는 동일한 value를 가진 Node가 곧 공통 부모Node가 되는 것이고 이렇게 얻은 공통 부모Node의 인덱스가 시작Node와 비교해야할 depth가 되며 목적지Node가 시작해야할 최단루트의 출발지점이 되겠다
이렇게 depth의 차이만큼 "U"를 추가하며 목적지 Node의 최단루트를 타고가며 pair로 넣어둔 string을 추가해주면 우리가 원하는 최단루트가 나온다
- 시간복잡도:
- DFS에서 O(n) * 2 + 공통 부모찾기에서 O(n)... O(3n) 으로 그냥 O(n)이 되겠다
풀이 결과:
정답이다!
하지만 꽤나 느리고 공간도 많이 잡아먹는것으로 나왔다
배운 점 및 코드:
using name = data type 을 배웠다 가독성이 늘었다!
공통 조상 알고리즘이란게 있나보다 공통 조상 == 공통 부모라고 보면 되는데, 이를 탐색하는데 있어 BackTracking DFS를 사용을 두번이나 한 나로서는 이 알고리즘고가 굉장히 비교되는 일이었다
이부분을 공부해야겠다
/**
* 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:
// 덱을 사용하는 이유로는 양 끝에서의 삽입과 삭제가 O(1)의 시간 복잡도로 가능하며
// 인덱스를 통한 참조도 O(1)으로 가능하기 때문이다
using dqis = deque<pair<int, string>>;
string getDirections(TreeNode* root, int startValue, int destValue) {
dqis startRoute, destRoute;
int uCount = 0, commonParentIndex = 0;
string result = "";
dfsGetRoute(root, startRoute, startValue, "");
dfsGetRoute(root, destRoute, destValue, "");
// startValue와 공통부모의 높이 차를 구해서 "U" 개수 구하기
// destRoute 내에서 공통 부모의 인덱스 구하기
for (int i = 0; i < startRoute.size() && i < destRoute.size(); ++i) {
if (startRoute[i].first == destRoute[i].first)
commonParentIndex = i;
else
break;
}
uCount = startRoute.size() - commonParentIndex - 1;
// "U" 개수에 맞게 추가
for (int i = 0; i < uCount; ++i) {
result += "U";
}
// destRoute 순회하면서 "L", "R" 추가
for (size_t i = commonParentIndex + 1; i < destRoute.size(); ++i) {
result += destRoute[i].second;
}
return result;
}
// BackTracking 사용하여 최소화
int dfsGetRoute(TreeNode *node, dqis &route, int value, string dir) {
if (!node)
return (0);
route.push_back(make_pair(node->val, dir));
if (node->val == value)
return (1);
if (dfsGetRoute(node->left, route, value, "L"))
return (1);
if (dfsGetRoute(node->right, route, value, "R"))
return (1);
route.pop_back();
return (0);
}
};