Leetcode - 114. Flatten Binary Tree to Linked List

문제

주어진 이진 트리를 링크드 리스트로 변환하라. 리스트의 순서는 트리의 preorder 순회 순서이다.

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

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

해결 recursion

구조를 보면 root->right에 gen_list(root->left), 즉 root->left 통째로 리스트로 변환된 헤드를 등록하고. 기존 root->right는 tmp에 저장해두었다가, root->right의 가장 마지막 right에 gen_list(tmp)한것을 등록한다.

주의할 사항은 root->right노드가 위에서 저장했던 tmp노드와 동일하면 바로 gen_list(tmp)해야한다(아래 <- 이 부분).

좋은 문제였다!

struct TreeNode *gen_list(struct TreeNode *root)
{
    if (root == NULL)
        return NULL;
    struct TreeNode *tmp = root->right;
    if (root->left) {
        root->right = gen_list(root->left);
        root->left = NULL;
    }
    if (root->right) {
        struct TreeNode *right_last = root->right;
        if (right_last == tmp) {  		// <- 이 부분
            right_last = gen_list(tmp);
        } else {
            for (; right_last->right != NULL; right_last = right_last->right)
                ;
            right_last->right = gen_list(tmp);
        }
    }
    return root;
}

void flatten(struct TreeNode* root){
    root = gen_list(root);
}