Python으로 이진 트리의 루트 노드를 변경하는 방법

이진 트리와 그 트리의 리프(leaf) 노드에 위치한 하나의 노드가 주어졌다고 가정해 봅시다. 우리가 해야 할 작업은 이 리프 노드를 이진 트리의 새로운 루트 노드로 만드는 것입니다. 다음과 같은 규칙에 따라 트리를 재구성할 수 있습니다.

노드에 왼쪽 자식이 있었다면, 해당 자식은 오른쪽 자식이 됩니다.
노드의 기존 부모는 그 노드의 왼쪽 자식이 됩니다. 이 과정에서 부모 노드가 해당 노드를 가리키던 링크는 null이 되므로, 부모 노드는 자식을 하나만 갖게 됩니다.

트리의 노드 구조는 다음과 같습니다.

TreeNode:
    data: <integer>
    left: <pointer of TreeNode>
    right: <pointer of TreeNode>
    parent: <pointer of TreeNode>

변환이 완료된 트리의 루트 노드를 반환해야 합니다.

예를 들어, 아래와 같은 트리가 입력으로 주어지고,

Python으로 이진 트리의 루트 노드를 변경하는 방법

새로운 루트가 8이라면, 변환된 트리의 중위 순회(inorder) 결과는 다음과 같습니다.

2, 3, 4, 5, 7, 6, 8

즉, 트리의 새로운 루트 노드는 8이 됩니다.

문제 해결 접근 방법

이 문제는 재귀 함수를 사용하여 해결할 수 있습니다. 핵심 아이디어는 리프 노드부터 시작해 루트까지 거슬러 올라가면서 각 노드의 부모-자식 관계를 뒤집는 것입니다. 구체적인 단계는 다음과 같습니다.

helper(node, new_par) 함수를 정의합니다.
- 현재 노드가 루트와 같다면:
  - 노드의 parent를 new_par로 설정합니다.
  - 노드의 왼쪽 자식이 new_par와 같으면 left를 null로 만듭니다.
  - 노드의 오른쪽 자식이 new_par와 같으면 right를 null로 만듭니다.
  - 루트를 반환합니다.
- 노드의 왼쪽 자식이 존재하면, 그 자식을 오른쪽 자식으로 이동시킵니다.
- 부모의 왼쪽 자식이 현재 노드라면, 부모의 left를 null로 설정합니다.
- node.left = helper(node.parent, node)를 호출하여 부모를 왼쪽 자식으로 연결합니다.
- 노드의 parent를 new_par로 갱신한 후 노드를 반환합니다.
마지막으로 helper(leaf, None)을 호출하여 결과를 반환합니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

예제 코드

import collections
class TreeNode:
    def __init__(self, data, left = None, right = None, parent = None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent
    def insert(temp,data):
        que = []
        que.append(temp)
        while (len(que)):
            temp = que[0]
            que.pop(0)
            if (not temp.left):
                if data is not None:
                    temp.left = TreeNode(data, parent = temp)
                else:
                    temp.left = TreeNode(0, parent = temp)
                break
            else:
                que.append(temp.left)
            if (not temp.right):
                if data is not None:
                    temp.right = TreeNode(data, parent = temp)
                else:
                    temp.right = TreeNode(0, parent = temp)
                break
            else:
                que.append(temp.right)
def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree
def search_node(root, element):
    if (root == None):
        return None
    if (root.data == element):
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2
def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end = ', ')
        print_tree(root.right)
def solve(root, leaf):
    def helper(node, new_par):
        if node == root:
            node.parent = new_par
            if node.left == new_par:
                node.left = None
            if node.right == new_par:
                node.right = None
            return root
        if node.left:
            node.right = node.left
        if node.parent.left == node:
            node.parent.left = None
        node.left = helper(node.parent, node)
        node.parent = new_par
        return node
    return helper(leaf, None)
root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))
print_tree(root)

입력

root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))

출력

2, 3, 4, 5, 7, 6, 8,

위 코드에서 solve() 함수는 지정된 리프 노드를 새로운 루트로 삼도록 트리 전체를 재구성하며, print_tree() 함수는 중위 순회 방식으로 변환된 트리의 노드 값을 출력합니다. 시간 복잡도는 트리의 높이에 비례하는 O(h)이며, 공간 복잡도 역시 재귀 호출 스택으로 인해 O(h)입니다.