TIL - 이진 트리, 재귀 구현

문제

- 이진 트리의 기본 구조를 구현합니다.
- 각 노드는 최대 2개의 자식(왼쪽, 오른쪽)을 가집니다.
- 전위, 중위, 후위 순회를 구현합니다.
- 각 노드가 최대 2개의 자식 노드(왼쪽, 오른쪽)를 가질 수 있는 트리 구조.

 

[알고리즘] 트리 구조와 사용하는 이유, 이진 검색 트리

 

 

 

문제풀이

class TreeNode:
    """이진 트리 노드"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def preorder(root):
    """전위 순회: 루트 → 왼쪽 → 오른쪽"""
    result = []
    
    if root is None :
        return result
    
    result.append(root.value)
    result.extend(preorder(root.left))
    result.extend(preorder(root.right))
    
    return result

def inorder(root):
    """중위 순회: 왼쪽 → 루트 → 오른쪽"""
    result = []
    
    if root is None :
        return result
    
    result.extend(inorder(root.left))
    result.append(root.value)
    result.extend(inorder(root.right))
    
    return result

def postorder(root):
    """후위 순회: 왼쪽 → 오른쪽 → 루트"""
    result = []

    if root is None :
        return result
    
    result.extend(postorder(root.left))  # obj 가 배열이니까 extend 사용하여 붙여주기.
    result.extend(postorder(root.right))
    result.append(root.value)
    
    return result

 

이진 트리의 서브 트리는 또 하나의 이진 트리 구조이기 때문에 재귀로 구현하였다. 전위, 중위, 후위 순회는 순서만 다를 뿐 구현 자체는 똑같다. List 의 extend 메서드를 알게되었다. append (가장 마지막에 요소 추가) 로 하니, 배열에 배열을 추가하여 [1, [2, [4], [5]], [3]] 형태로 추가되었다. 

 

 

list.extend() 메서드

리스트 끝에 다른 반복 가능한 객체 (iterable/ 리스트, 튜플, 문자열 등)의 모든 항목을 풀어 넣어서 리스트를 확장한다. 새로 더해지는 리스트의 길이에 비례하여 시간이 걸린다. 시간 복잡도는 O(n) 이다. 

 

 

현재 코드는 extend 때문에 최악의 시간 복잡도가 O(n^2) 이 된다. 더 개선해볼 방법 없을까 .... 고민하다가 재귀 함수를 따로 빼고, 상위의 result에 append 하는 방식으로 하면 어떨까 ... 공유 배열을 사용하는 방식으로.

 

def postorder(root):
    """후위 순회: 왼쪽 → 오른쪽 → 루트"""
    result = []
    _postorder_helper(root, result)
    return result

def _postorder_helper(root, result):

    # root 가 빈값일 시 반환
    if root is None :
        return result
    
    # 왼쪽 
    _postorder_helper(root.left,result)  # obj 가 배열이니까 extend 사용하여 붙여주기.
    
    # 오른쪽
    _postorder_helper(root.right,result)
    
    # 루트
    result.append(root.value)
    
    return

 

 

배열을 복사하고 붙여넣는 과정에서 효율이 떨어졌던 거니까 .. 근데 일단 리턴 값 보면서 수정했는데 재귀는 역시 어렵다. 보면서 수정해야함 ..

 

 

어려웠던 점

1. 재귀에서 상위 함수로 보내는 return 값에 대해 가공이 어렵다.
   • 잘못하면 데이터가 갱신되고, 원하는 형태가 아니게 된다. 이에 대해 재귀의 회귀 방식에 대해 더 깊은 이해가 필요할 것 같다. 어렴풋이 감은 잡았는데 여전히 어렵다. 머리를 20번 정도 굴리면 해당 문제에 대해 어렴풋하게 나마 이렇게 해야하나 생각이 든다 ...
2. 헬퍼 함수를 안에 넣었을 때는 ? (파이썬 함수 설계 원리)
   • 안에 두는 경우
     • helper 함수는 postorder 함수가 호출될 때마다 새로 정의된다. (오버헤드 약간 발생)
     • postorder 외부에서는 내부 헬퍼 함수가 안보임
     • 클로저 : 내부 함수는 바깥 함수의 변수에 접근 가능
   • 밖에 두는 경우
     • 함수 정의가 한 번만 이루어짐
     • 다른 함수에서도 재사용 가능
     • 네임스페이스가 노출됨 (관례적으로 _ 접두사로 내부용이라는 컨벤션 표시)
3. extend 의 사용처
   • 재귀에서 리스트로 결과를 모아서 반환할 때 (리스트 병합)
   • 제자리 수정 : 기존 리스트의 메모리 주소를 유지한 채 내부 값만 변경
   • 다양한 iterable 병합 : 리스트, 튜플, 세트, 문자열 등의 요소를 리스트 뒤에 붙일 수 있다.
     • iterable 
       • 반복 가능한 객체
       • for 문의 in 키워드 뒤에 사용 가능
       • 시퀀스 자료형 : 리스트, 튜플, 문자열, 범위
       • 컬렉션 자료형 : 딕셔너리, 집합
4. list 에서의 += 
   • a.extend([4,5]) 
   • a += [4,5]
   • a = a + [4,5]
   • += 연산자는 내부적으로 __iadd__ 메서드를 호출한다. 
   • extend 와 동일하게 메모리 주소가 바뀌지 않고 기존 리스트 객체에 데이터가 추가됨
   • + 연산자와의 차이 : 두 리스트를 합쳐서 완전히 새로운 리스트 객체를 메모리에 새로 생성함.