[Algorithm] 이진 트리의 재구성

이진 트리: Binary Tree

이진 트리 예시

 

- 루트 노드와 두 개의 서브 트리로 구성되는 노드들의 집합

• 공집합은 이진 트리
• 서브트리도 이진 트리 (재귀적으로 정의)
• 왼쪽 서브 트리와 오른쪽 서브 트리는 서로소 (disjoint)
• 서로소: 여러 개의 수들 사이에 1 이외의 공약수가 없음 (서로 겹치는 소인수가 없음)

---

공집합이 이진 트리가 되는 이유

- 루트 노드가 있지만 서브 트리가 null일 경우에도 '서브트리도 이진 트리'라는 조건에 만족하기 위해 '공집합도 이진 트리'라고 해야 함

- 두 개의 노드만을 자식 노드로 갖는 이진 트리의 규칙을 벗어나지 않도록 만들어주기 위함 

---

이진 트리의 순회: Binary Tree Traversal

이진 트리 순회 예시

• 전위 순회 (Preorder Traversal): 루트 노드 먼저 방문 (V L R 순)
• 중위 순회 (Inorder Traversal): 왼쪽 하위 노드 방문 후 루트 노드 방문 (L V R 순)
• 후위 순회 (Postorder Traversal): 하위 노드 모두 방문 후 루트 노드 방문 (L R V 순)

---

이진 트리 순회 예시

---

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

- 전위 순회와 순회 결과가 주어지면 이진 트리를 재구성 할 수 있는가?

class TreeNode:
	def __init__(self, item = 0, left = None, right = None):
    	self.item = item
        self.left = left
        self.right = right
        
class Solution:
	def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    # int 리스트를 가진 preorder, inorder가 주어졌을 때, 이진 트리를 return 하라

// 그림으로 된 설명은 출처의 영상 (3분 55초부터) 참고

1. Preorder의 첫 번째 노드는 루트 노드이고, Inorder에서 루트 노드의 위치를 찾을 수 있음
2. Inorder에서 루트 노드의 왼쪽/오른쪽 노드들은 각각 왼쪽/오른쪽 서브트리
3. 왼쪽/오른쪽 서브트리의 크기를 안다면, Preorder의 왼쪽/오른쪽 Preorder를 결정할 수 있음
4. 루트 노드의 왼쪽/오른쪽 서브 트리의 Pre/Inorder를 재귀 호출을 통해 연결하면 이진 트리 구성 가능

---

구현된 코드

class Solution:
	def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    	if len(preorder) == 0:
        	return None
        # 트리의 길이가 0이면 Null return
        else:
        	root, pos = preorder[0], inorder.index(preorder[0])
            # preorder의 첫번째 원소([0])가 루트 노드
            # inorder에서 루트 노드(preorder[0])을 index 번호로 찾으면
            left = self.buildTree(preorder[1:pos + 1], inorder[:pos])
            right = self.buildTree(pos + 1:], inorder[pos + 1:])
            # left, right 서브 트리의 preorder와 inorder를 재귀호출 하면 됨
            return TreeNode(root, left, right)

---

출처

1. 주니온TV 아무거나연구소 - 이진 트리의 재구성 https://www.youtube.com/watch?v=PYQA_8B899A&list=PLHqxB9kMLLaNIvuYT6NgXsIt782lS3xiD&index=5