[LeetCode] 114. Flatten Binary Tree to Linked List

말하는 감자·2024년 12월 5일

DFS binary tree data structure leetcode linked list preorder python stack tree traversal 리트코드 연결 리스트 이진 트리 자료구조 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

27/32

오늘부터는 본격적으로 medium레벨의 연결 리스트 유형의 문제를 풀어보았습니다. 한 번 살펴볼까요?

1. 오늘의 학습 키워드

Linked List
Binary Tree
Tree Traversal
Preorder
Stack

2. 문제: 114. Flatten Binary Tree to Linked List

단계: Medium
주제: Linked List, Stack, Tree, Depth-First Search, Binary Tree
출처: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/description/

Description

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Example 1:

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

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up:

Can you flatten the tree in-place (with O(1) extra space)?

3. 문제 풀이

step1. 문제 이해하기

이번 문제는 이진 트리가 주어졌을 때, 트리를 연결 리스트형태로 평탄화하는 문제입니다. 생성되는 연결 리스트는 동일한 TreeNode 클래스를 사용해야 하며, 오른쪽 자식 포인터(right)는 리스트에서 다음 노드를 가리켜야 하고, 왼쪽 자식 포인터(left)는 항상 null이어야 합니다. 즉, 연결 리스트는 이진 트리의 전위 순회 순서와 동일한 순서여야 합니다.

“주어진 트리 노드를 전위 순회로 나타내라!” 이렇게 이해하면 될 것 같습니다.

입출력을 살펴보도록 하겠습니다.

Input:
- 트리의 노드 개수는 0이상 2000이하입니다.
- 트리의 전위 순회는 노드 개수만큼의 시간복잡도로 이뤄지기 때문에 여유있을 것으로 보입니다.
Output:
- 변환된 연결 리스트를 반환합니다.
- 반환 타입을 보면 함수는 값을 반환하지말고 입력값을 in-place 수정해야 한다고 합니다.
- 즉, 기존의 트리를 바로 변경해야 한다는 것을 알 수 있습니다.

Step2. 문제 분석하기

주어진 이진 트리를 연결 리스트로 반환해야 합니다. 반환 시, 함수의 입력값으로 주어지는 트리를 직접 반환해야 합니다. 즉, 따로 반환값은 존재하지 않습니다.

생성되는 연결 리스트는 트리의 전위 순회 순서대로 노드를 방문했을 때와 동일하기 때문에 전위 순회 알고리즘으로 구현하면 해결될 것 입니다.

전위 순회는 재귀 방법과 스택 방법이 있습니다. 이 두 가지 모두를 사용해서 구현을 진행하도록 하겠습니다.

하지만, 이 방법은 공간 복잡도가 무조건 노드 개수만큼 소요됩니다.

주어진 문제에 O(1)로 구현을 할 수 있겠냐라는 Follow up이 있었습니다.. 이 방법은 Morris Traversal이란 방법이 있는데, 저는 이 방법은 스킵하도록 하겠습니다 (코테에서는 거의 나오지 않는것 같습니다).

그럼 이대로 코드 설계를 해보도록 하겠습니다.

Step3. 코드 설계하기

Recursion (Preorder Traversal) 방법

전위 순회로 노드 방문:
- preorder라는 재귀 함수를 정의하여 트리를 전위 순회합니다.
- 각 노드를 방문할 때, 노드를 nodes 리스트에 추가합니다.
리스트 기반 트리 평탄화:
- 전위 순회로 얻은 nodes 리스트를 기반으로 트리를 평탄화합니다.
- nodes[i].right를 nodes[i+1]로 설정하여 다음 노드를 연결합니다.
- nodes[i].left를 None으로 설정하여 왼쪽 자식 노드를 제거합니다.
시간 복잡도 및 공간 복잡도:
- 시간 복잡도: O(n) (모든 노드를 한 번씩 방문).

Stack (Iterative) 방법

초기화:
- 스택을 생성하고, root 노드를 스택에 추가합니다.
반복적으로 노드 처리:
- 스택에서 노드를 꺼내 현재 노드(current)로 설정합니다.
- 현재 노드의 오른쪽 자식이 있다면 스택에 추가합니다.
- 현재 노드의 왼쪽 자식이 있다면 스택에 추가합니다.
- 스택의 마지막 노드를 current.right로 설정하여 연결 리스트를 만듭니다.
- current.left를 None으로 설정하여 왼쪽 자식을 제거합니다.
시간 복잡도 및 공간 복잡도:
- 시간 복잡도: O(n) (모든 노드를 한 번씩 방문).

Step4. 코드 구현하기

Stack

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    # 2. Stack
    def flatten_stack(self, root):
        # https://leetcode.com/problems/flatten-binary-tree-to-linked-list/submissions/1470755853
        """
        :type root: Optional[TreeNode]
        :rtype: None Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        
        stack = [root]
        
        while stack:
            current = stack.pop()
            
            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
            
            if stack:
                current.right = stack[-1]
            current.left = None

코드 설명
- 스택을 사용하여 반복적으로 노드를 처리합니다.
- 현재 노드의 오른쪽 자식과 왼쪽 자식을 스택에 추가합니다.
- 스택의 마지막 노드를 현재 노드의 오른쪽 자식으로 설정하고, 왼쪽 자식을 제거합니다.
시간 복잡도: $O(n)$
- 모든 노드를 한 번씩 방문합니다.
결과: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/submissions/1470755853

Recursion

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
# 1. Recursion
    def flatten_recursive(self, root):
        # https://leetcode.com/problems/flatten-binary-tree-to-linked-list/submissions/1470756133
        """
        :type root: Optional[TreeNode]
        :rtype: None Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        
        nodes = []
        def preorder(node):
            if node:
                nodes.append(node)
                preorder(node.left)
                preorder(node.right)
        
        preorder(root)
        for i in range(len(nodes)-1):
            nodes[i].right = nodes[i + 1]
            nodes[i].left = None

코드 설명
- 전위 순회로 모든 노드를 nodes 리스트에 저장합니다.
- 리스트를 순회하며:
  - 각 노드의 right를 다음 노드로 연결.
  - 각 노드의 left를 None으로 설정.
- 결과적으로 트리가 연결 리스트로 평탄화됩니다.
시간 복잡도: $O(n)$
- 모든 노드를 한 번씩 방문합니다.
결과: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/submissions/1470756133