[파이썬 알고리즘 인터뷰] 트리

• 트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합
  • 재귀로 정의된 자기 참조 자료구조
  • 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다
  • 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수
  • 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리
  • 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1
  • 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트
• 이진 트리: 가장 널리 사용되는 트리 자료구조
  • m-ary 트리(다항 트리, 다진 트리): 각 노드가 m개 이하의 자식을 갖는 트리
  • 이진 트리: m=2 인 경우
  • 이진 트리 유형(표준화되어있지 않아 위키피디아 기준)
    • 정 이진 트리(Full Binary Tree): 모든 노드가 0 또는 2개의 자식 노드를 갖는다
    • 완전 이진 트리(Complete Binary Tree): 마지막 레벨 제외, 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다
    • 포화 이진 트리(Perfect Binary Tree): 모든 노드가 3개의 자식노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다

104. maximum depth of binary tree

- BFS -> 탐색 반복 횟수 하나하나가 곧 깊이

 

543. diameter of binary tree

- DFS -> 리프 노드까지 탐색한 후 부모로 거슬러 올라가며 각 노드에서의 상태값(리프에서부터의 거리) 계산 및 최장거리 값 갱신

• 최장거리 변수가 불변객체이므로 클래스 변수로 선언하여 중첩 함수에서 재할당해도 별도의 로컬 변수로 처리되지 않도록 한다

687. longest unknown path

- DFS -> 리프 노드까지 탐색하고 거슬러 올라가며 각 노드에서 자식과 값이 같은지에 따라 상태값 계산 및 최장거리 값 갱신

• dfs 함수의 return 값이 해당 노드에 (상태값으로서) 부여된다

226. invert binary tree

- 재귀 DFS -> 상향식 스왑

- 반복 BFS -> 하향식 스왑

- 반복 DFS -> 하향식 스왑

- 반복 DFS 후위 순회 -> 하향식 스왑

- 내 풀이: 솔루션 함수의 재귀가 아닌, dfs 함수 생성하여 재귀 -> 코드가 더 간결하지 못하지만 성능은 같다

* 자식 노드의 상태값으로 부모 노드의 상태값 계산할 필요가 있는지에 따라 구조 결정(해당 노드의 존재 유무 vs 자식 노드 존재 유무)(솔루션 함수 활용 vs dfs함수 생성)

 

617. merge two binary trees

- 재귀 DFS -> 각 탐색마다 새 노드에 값과 자식 노드 설정(재귀)

* return에서 or/and 연산

[python] return에서 or/and 연산자 사용법

 

297. serialize and deserialize binary tree

* 직렬화: 논리적인 구조인 이진트리를 파일이나 디스크에 저장하기 위해 물리적인 형태로 바꿔주는 작업 (↔ 역직렬화)

* 모든 이진 트리는 배열로 표현가능(대게 인덱스 1부터 사용) -> 인덱스를 알면 깊이 정보, 부모와 자식 노드가 배열 어디에 위치하는지 바로 알아낼 수 있음

- BFS (리스트에서 트리의 형태가 더 직관적으로 보이게끔) -> 직렬화: 현재 노드 값 존재 여부에 따라 리스트에 추가

-> 역직렬화: input data를 이용해 자식 노드 값 존재 여부에 따라 트리 구성

 

110. balanced binary tree

- 재귀 DFS -> 각 노드에 높이 값 부여 및 자식 노드 높이차 계산 (높이차가 1 초과 시 해당 노드에 -1 부여)

- 내 풀이: ans 변수에 true 할당하고 높이차가 1 초과 시 ans 변수 값 false 재할당

 

310. minimum height trees

- 리프 제거 반복하여 가장 가운데에 위치한 1개 또는 2개의 노드가 루트가 될 수 있음

- edges에 한 개만 있는 노드가 리프노드

- 무방향일때는 그래프 딕셔너리에 양쪽방향으로 다 입력, 지울때 둘다 지우기

 

• 이진 탐색 트리(BST): 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄지고, 오른쪽 서브트리에는 같거나 큰 값들을 지닌 노드들로 이뤄진 트리
  • 이렇게 값에 따라 정렬된 트리이므로 탐색 시 시간 복잡도가 O(logn)이다
  • 좌우 서브트리를 랜덤하게 구성하여 트리를 만들때 운이 나쁘면 불균형이 올 수 있고, 최악은 탐색 시 O(n)
  • 이렇게 균형이 잘 안맞는 경우에는 이진 탐색 트리의 장점을 전혀 살릴 수 없으므로 균형을 맞줘준다
• 자가 균형(높이 균형) 이진 탐색 트리: 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리
  • 루트의 높이로 불균형과 균형을 구분할 수 있고, 이 높이를 작게 할수록 탐색 시 효율적이다
  • 대표적인 형태로 AVL트리와 레드-블랙 트리 등

108. convert sorted array to binary search tree

- 배열의 중앙값을 노드에 삽입하고 그 자식들을 남은 배열의 절반들로 각각 재귀적으로 구성(분할 정복)

-> 인덱스 변수 할당하여 시작하고 재귀로 트리 생성

 

1038. binary search tree to greater sum tree

- DFS -> 중위 순회(RNL)하며 누적된 값으로 각 노드의 값 갱신

 

938. Range Sum of BST

- 재귀 DFS로 브루트 포스 탐색 (내 풀이)

- 재귀 DFS로 가지치기 하며 탐색 -> dfs 함수 return 값이 누적된 노드 값

- 반복 DFS로 가지치기 하며 탐색

- 반복 BFS로 가지치기 하며 탐색

 

783. Minimum Distance Between BST Nodes

- 재귀 DFS로 중위 순회하며 현재 노드 값과 직전 탐색 노드 값의 차이 계산 및 최소차이값 갱신

- 반복 DFS로 동일 알고리즘

# 모두 동일한 코드

if root.left:
    self.minDiffInBST(root.left)

self.ans = min(self.ans, root.val - self.prev)
self.prev = root.val

if root.right:
    self.minDiffInBST(root.right)

return self.ans
#####################################################
if root:
    self.minDiffInBST(root.left)

    self.ans = min(self.ans, root.val - self.prev)
    self.prev = root.val

    self.minDiffInBST(root.right)

return self.ans
#####################################################
def dfs(node):
    if not node:
        return

    dfs(node.left)
    self.ans = min(self.ans, node.val - self.prev)
    self.prev = node.val
    dfs(node.right)

dfs(root)
return self.ans

• 재귀구조 DFS일때: LNR 중위순회 -> 노드 값 오름차순 탐색, RNL 중위순회 -> 노드 값 내림차순 탐색 (BST에 한해)

• 트리 순회: 그래프 순회의 한 형태로 트리에서 각 노드를 정확히 한 번 방문하는 과정
  • DFS -> 전위, 중위, 후위 ... (이후 생략)

 

105. Construct Binary Tree from Preorder and Inorder Traversal

- 전위 순회 결과로 중위 순회 분할 정복

* 전위, 중위, 후위 순회 중 2가지만 있어도 이진 트리 복원 가능