Daily Coding Problem을 subscribe 하면 매일 한 개의 코딩 문제를 이메일로 받을 수 있다.

DCP #3

이 문제는 실제 구글 면접에서 나온 질문이다.

이진 트리의 루트가 주어졌을 때, serialize(root)deserialize(s)를 수행하는 함수를 작성하라. serialize(root)는 이진 트리를 문자화시켜 문자열을 반환하고 deserialize(s)는 문자열로 부터 다시 트리를 구성한 후 루트 노드를 반환한다.

예를들어, 아래와 같은 노드 클래스가 있을 때

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

다음의 테스트를 패스해야 한다.

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

원문 읽기


코드

class Node
    attr_accessor :val, :left, :right

    def initialize(val, left=nil, right=nil)
        @val = val
        @left = left
        @right = right
    end
end

def serialize(node)
    if node == nil 
        return 'nil'
    end

    left_str = serialize(node.left)
    right_str = serialize(node.right)

    return "#{node.val} #{left_str} #{right_str}"
end

def deserialize(s)
    tokens = s.split(' ')
    des_helper tokens
end

def des_helper(tokens)
    current = tokens.first
    tokens.shift

    if current == 'nil'
        return nil
    end

    curr_node = Node.new(current)
    curr_node.left = des_helper(tokens)
    curr_node.right = des_helper(tokens)

    return curr_node
end

설명

serialize(node)함수는 처음에 DFS로 하려다가 망해서(지금 생각해보면 하긴 했다. 그런데 필자가 작성한 코드의 결과를 필자가 이해하지 못했었다)재귀를 사용한 preorder로 방향을 바꿨다.

preorder는 트리에서 순회하는 세 가지 방법 중 하나로 아래와 같은 순서로 동작한다.

  1. 현재 노드 방문 (visit)
  2. 현재 노드의 왼쪽 자식으로 이동 (left)
  3. 현재 노드의 오른쪽 자식으로 이동 (right)

위 방법을 이용해 작성한 코드가 serialize(node)이다.

def serialize(node)
    # 재귀함수 종료 (terminating condition)
    if node == nil 
        return 'nil'
    end

    # 현재 노드의 왼쪽 자식들의 값
    left_str = serialize(node.left)
    # 현재 노드의 오른쪽 자식들의 값
    right_str = serialize(node.right)

    # 현재 노드 값뒤에 자식들의 값을 이어 붙힌다.
    # 각 노드의 값들은 공백으로 분리
    return "#{node.val} #{left_str} #{right_str}"
end

deserialize(s)의 경우 트리가 serialize될 때 사용된 경로를 그대로 따라가며 재구성 해야한다.
그렇기 때문에 deserialize 역시 preorder 방법을 사용한다.

그전에 우선 문자열 형태로 있는 노드들을 각각의 노드로 분리해줘야 한다.
공백으로 구분되어 있으니 아래와 같이 분리하고 helper 함수에 분리된 값을 넘겨준다.

def deserialize(s)
    # 문자열에서 모든 노드들을 분리하고 helper 함수에 넘겨준다.
    tokens = s.split(' ')
    des_helper tokens
end

분리된 노드들을 앞에서부터 차례대로 트리에 집어넣는다.
잠깐? 왠지 Queue를 사용해야 할 것 같은 느낌이 든다 (아님 말고).

루비에서는 배열로 큐와 같은 작업을 할 수 있기때문에 배열을 사용했다.

def des_helper(tokens)
    # 큐에서 값을 가져온다.
    current = tokens.first
    tokens.shift

    if current == 'nil'
        return nil
    end

    # 새로운 노드를 만들고 현재 노드에 큐에서 나온 값을 대입
    curr_node = Node.new(current)
    # 재귀를 사용해 새로운 노드의 왼쪽과 오른쪽 자식들의 값을 가져온다.
    curr_node.left = des_helper(tokens)
    curr_node.right = des_helper(tokens)

    # 재구성된 트리의 root를 반환
    return curr_node
end

문자화를 하면서 모든 노드들을 방문하기 때문에 시간복잡도는 O(n)이고,
공간복잡도 또한 스택 프레임 때문에 O(n)이 된다.

관련 글


Blog: https://muicode.github.io
DCP GitHub: https://github.com/muicode/DCP