114. Flatten Binary Tree to Linked List
문제링크: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Binary Tree를 pre-order순으로 right로 연결되어있는 연결리스트로 만드는 문제다.
Solution
1. Recursion
가장 먼저 전위순회를 통해 트리를 탐색하는 것으로 시작해보기로 했다. DFS탐색을 하며 전위순회를 하는 방식으로 현재 노드를 dummy로 시작하는 새로운 리스트에 잇는 방법으로 구현할 수 있었다. 전위순회시에 주의할 점은 순회를 하면서 left와 right를 바꾸기 때문에 이를 미리 저장해놓고 탐색을 이어나갈 때 재사용 한다는 점이다.
Algorithm
- 새 연결리스트 역할을 할
dummy를 설정해준다. cur는 연결리스트를 이어줄 리스트의 끝 포인터다.- 탐색을 시작하면
node.left와node.right를 미리 저장해준다. - 현재
node를cur.right와 이어주고 왼쪽포인터를null로 초기화한다. - 앞서 저장해 놓았던 다음 탐색을 진행해 전위순회 재귀를 완성한다.
var flatten = function(root) {
// DFS
const dummy = new TreeNode(-1);
let cur = dummy;
const dfs = (node) => {
if (!node) return;
// Save next nodes then preorder
const left = node.left;
const right = node.right;
cur.right = node;
node.left = null;
cur = node;
dfs(left);
dfs(right);
}
dfs(root);
return dummy.next;
};
시간 복잡도는 탐색에 필요한 노드 개수 O(n), 공간 복잡도는 재귀를 통해 발생하는 일종의 스택형식의 O(n)의 공간이 필요하다.
2. Morris traversal
문제의 follow-up을 위해 공간 복잡도 O(1)의 알고리즘을 구현해 보기로 했다. 노드의 우측으로 연결된 부분은 이미 순서대로 정렬되어있다. 다만 왼쪽 노드들을 우측노드 사이에 연결해준다면 이를 연결리스트로 변환시킬 수 있다. 이 평탄화 작업을 위해 현재노드 -> 왼쪽노드 ~ 왼쪽노드의 가장 오른쪽 -> 오른쪽노드로 연결하는 것을 반복한다.
Algorithm
root노드를cur노드로 지정하고 탐색한다.- 왼쪽노드가 없는 경우는 이미 연결리스트의 형태를 만족하므로 넘어간다.
- 왼쪽노드가 있는 경우 왼쪽노드를
runner로 지정한다. runner는runner.right가 가능할 때까지 진행해 왼쪽 노드의 가장 오른쪽을 가리킨다.- 왼쪽 <- 현재 -> 오른쪽 의 형태를 현재 -> 왼쪽 ... runner -> 오른쪽의 형태로 연결한다.
- 현재노드에 대한 평탄화를 완료하여 왼쪽노드를 삭제한 것이 되고 다음 오른쪽 노드에서도 같은 방법으로 반복한다.
var flatten = function(root) {
// O(n) / O(1) solution
// Morris Traversal : 왼쪽노드를 부모 노드와 오른쪽노드 사이에 삽입하는 알고리즘
// 오른쪽을 끊고 왼쪽노드의 가장 오른쪽(runner)과 잇는다.
const result = root;
let cur = root;
while (cur) {
// 왼쪽이 존재하는 경우 변경
if (cur.left) {
// 왼쪽 노드의 오른쪽 끝노드를 runner
let runner = cur.left;
while (runner.right) {
runner = runner.right;
}
// cur -> 왼쪽노드 ... 러너 -> 오른쪽노드 의 순서로 연결
const right = cur.right;
cur.right = cur.left;
cur.left = null;
runner.right = right;
}
cur = cur.right;
}
return result;
};
기존의 방식은 left와 right의 포인터를 기억해두고 우선 현재 노드작업과 left의 깊이 작업을 먼저 선행하고 돌아오기 위해 재귀스택을 필요로 한다. 하지만 Morris traversal은 추가적인 공간 할당 없이 현재 노드에 대한 평탄화 작업을 완료하고 추가적인 데이터 없이 다음 노드로 넘어가기 때문에 O(1)의 공간복잡도를 가지는 이점이 있다.
