114. Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

Flatten Binary Tree to Linked List - LeetCode

---

문제

Binary tree를 pre-order traversal 순서에 따라 linked list로 flatten 시키기

단, linked list는 주어진 binary tree의 구조에서 left child는 null이고 right child만 존재하도록 구성

---

풀이1

Binary tree의 pre-order traversal은 재귀함수로 간단하게 구할 수 있기 때문에 문제를 읽자마자 무지성으로 코딩을 시작할 수 있다.

1. Node를 방문한다.
2. 해당 node의 정보를 저장한다. -> pre
3. Left child를 target으로 다시 1번부터 반복한다.
4. Right child를 target으로 다시 1번부터 반복한다.
5. Left, right child를 nullptr를 가리키도록 바꾼다.
6. pre에 저장된 정보를 가지고 트리를 재구성한다.
   • 트리의 재구성은 단순히 right만 바꿔주면 되기 때문에 쓱싹 바꿔줄 수 있다.

코드를 살펴보자.

class Solution {
public:
    void go(TreeNode* _cur, vector<int>& _pre){
        if(!_cur) return;
        _pre.push_back(_cur->val);
        
        go(_cur->left, _pre);
        go(_cur->right, _pre);
        _cur = nullptr;
    }
    void flatten(TreeNode* root) {
        if(!root) return;
        
        vector<int> pre;
        go(root, pre);
        
        root = new TreeNode(pre[0]);
        auto cur = root;
        for(int i = 1; i<pre.size(); ++i){
            cur->right = new TreeNode(pre[i]);
            cur = cur->right;
        }
    }
};

결론부터 말하자면 위의 코드는 AC를 받을 수 없다. 처음에 한동안 맞왜틀에 빠져 있었는데 간과하고 있던 사실이 하나 있었다. 함수의 호출은 기본적으로 Call-by-Value, Call-by-Reference로 나눠진다는 점이다. 문제는 바로 flatten 함수에서 인자로 받은 root에 새로운 주소를 대입하고 있다는 점이다.

 

예를 들어 flatten 함수가 아래와 같이 호출된다고 가정하자.

int main(){
    TreeNode* tree;
	...
    flatten(tree);
    ...
}

이때 tree라는 변수가 0x1000을 가리키고 있다고 가정하면, root는 바로 이 0x1000을 복사해서 가져오게 될 것이다. 즉 tree라는 변수는 어떤 공간에 0x1000을 저장하고 있고, root는 tree와는 다른 공간에 0x1000을 가지고 있다. 따라서 root를 백날 바꿔봐야 tree라는 변수에 저장된 값은 바뀌지 않는다. 맨날 reference만 쓰다보니 이걸 간과하고 10분을 넘게 맞왜틀만 외치고 있었다. 수정한 코드는 아래와 같다.

 

class Solution {
public:
    void go(TreeNode* _cur, vector<int>& _pre){
        if(!_cur) return;
        _pre.push_back(_cur->val);
        
        go(_cur->left, _pre);
        go(_cur->right, _pre);
        _cur->left = nullptr;
    }
    void flatten(TreeNode* root) {
        if(!root) return;
        
        vector<int> pre;
        go(root, pre);
        
        auto cur = root;
        for(int i = 1; i<pre.size(); ++i){
            cur->right = new TreeNode(pre[i]);
            cur = cur->right;
        }
    }
};

 

아니면 아래와 같이도 쓸 수 있겠다.

 

class Solution {
public:
    void go(TreeNode* _cur, vector<TreeNode*>& _pre){
        if(!_cur) return;
        
        _pre.push_back(_cur);
        
        go(_cur->left, _pre);
        go(_cur->right, _pre);
        _cur->left = nullptr;
    }
    void flatten(TreeNode* root) {
        if(!root) return;
        
        vector<TreeNode*> pre;
        go(root, pre);
        
        for(int i = 1; i<pre.size(); ++i)
            pre[i - 1]->right = pre[i];
    }
};

 

이렇게 끝낼 수 있다면 좋겠지만 문제에서는 추가 공간의 공간 복잡도를 O(1)로 제한하고 이 문제를 풀 수 없냐고 도발을 해온다.

---

풀이2

사실 이것도 어렵지 않게 접근할 수 있다. Pre-order traversal이 어떤식으로 동작하는지만 알면 함수를 약간 수정하는 것만으로도 해결할 수 있다.

1. Node를 방문한다.
2. Right child를 임시 변수에 저장해둔다.
3. Left child를 right child로 옮겨준다.
4. (원래)Left child를 target으로 다시 1번부터 반복한다.
5. (원래)Right child를 target으로 다시 1번부터 반복한다.
6. (원래)Left child의 끝에 right child를 붙여준다.

코드는 아래와 같다.

class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == nullptr)
            return;
        
        auto left = root->left;
        auto right = root->right;
        
        root->left = nullptr;
        root->right = left;
        
        flatten(left);
        flatten(right);
        
        auto cur = root;
        while(cur->right != nullptr)
            cur = cur->right;
        
        cur->right = right;
    }
};

---

풀이3

코드를 써놓고 보니 (원래)right child를 어디에 붙일지를 return 값을 잘 활용하면 while문을 돌지 않고도 구할 수 있지 않을까란 생각이 들었다.

1. Node를 방문한다.
2. Leaf node인 경우 현재 node의 주소를 return 한다.
3. Left node를 방문하여 return 값을 저장한다. -> leftChild
4. Right node를 방문하여 return 값을 저장한다. -> rightChild
5. 만약 leftChild가 nullptr이 아닌 경우 left child가 존재하는 것이므로 leftChild의 right에 (원래)right를 붙여준다.
   • (원래)right는 필요 없으니 그냥 nullptr로 만들고 (원래)left와 swap한다.
6. leftChild가 nullptr인 경우 딱히 생각할 필요 없이 그대로 두면 된다.
7. Pre-order traversal에서 가장 마지막에 방문하는 node는 tree의 가장 오른쪽에 있는 leaf node일 것이므로, rightChild가 존재하는 경우 rightChild를, 그 외의 경우 leftChild를 return 해준다.

class Solution {
public:
    TreeNode* go(TreeNode* _cur){
        if(!_cur) return nullptr;
        if(!_cur->left && !_cur->right) return _cur;
        
        auto leftChild = go(_cur->left);
        auto rightChild = go(_cur->right);
        
        if(leftChild){
            leftChild->right = _cur->right;
            _cur->right = nullptr;
            swap(_cur->left, _cur->right);
        }
        return rightChild ? rightChild : leftChild;
    }
    void flatten(TreeNode* root) {
        go(root);
    }
};

 

이전 코드가 가장 빠른 속도가 7ms 정도가 나왔고 위의 코드가 6ms 정도가 나오는데, 이는 채점기의 상태에 따라 조금씩 달라질 수 있는 오차 범위 내의 수준이라 그다지 의미가 없다는걸 깨닫고 문제를 덮었다.

---

마치며

함수 호출 방식에 대해서 리마인드 하게 해주는 문제였다. 그리고 본격적으로 leet code를 사용하는건 사실 처음이나 다름이 없는데 nullptr 체크가 생각보다 까다롭다는 것과, 함수 완성형 문제이다 보니 (나의)재귀함수에서 stack overflow가 발생하지 않더라도 답을 잘못 구하면 (채점기의)재귀함수에서 stack overflow가 발생할 수 있으며 결과만 봐서는 이게 어디서 발생했는지를 알기가 쉽지 않다는 것을 느꼈다.

 

최근 여러모로 PS 능력이 예전 같지 않음을 느끼고 다시 시작하게 되었는데.. 확실히 더 열심히 해야겠다는 생각이 들었다.