이진 트리는 다양한 방식으로 저장될 수 있으며, 대표적인 저장 방식은 다음과 같습니다.

• 연결 리스트 기반 저장: 각 노드가 자식 노드를 가리키는 포인터를 포함하는 방식입니다.
• 배열 기반 저장: 루트 노드를 인덱스 0에 저장하고, 인덱스 i 노드의 왼쪽 자식은 2*i + 1, 오른쪽 자식은 2*i + 2에 저장하는 방식입니다. 이 방식은 특정 상황에서 효율적일 수 있으나, 일반적인 트리 구조에서는 덜 사용됩니다.

이진 트리를 탐색하는 두 가지 주요 방법은 다음과 같습니다.

• 깊이 우선 탐색 (DFS):

• 전위 순회 (Preorder Traversal): 현재 노드를 방문한 후 왼쪽 서브트리, 오른쪽 서브트리를 방문합니다. (중국어: 중좌우)

• 중위 순회 (Inorder Traversal): 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리를 방문합니다. (중국어: 좌중우)

• 후위 순회 (Postorder Traversal): 왼쪽 서브트리, 오른쪽 서브트리, 현재 노드를 방문합니다. (중국어: 좌우중) DFS는 재귀적 또는 반복적인 방식으로 구현할 수 있습니다.

• 너비 우선 탐색 (BFS):

• 레벨 순회 (Level Order Traversal): 트리의 각 레벨을 왼쪽에서 오른쪽으로 순서대로 방문합니다. 이 방식은 일반적으로 큐(Queue)를 사용하여 구현됩니다.

이진 트리 노드 정의

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

144. 이진 트리의 전위 순회

주어진 이진 트리의 루트 노드 root가 있을 때, 노드 값들의 전위 순회 결과를 반환하는 문제입니다.

해결 방법:

재귀 함수를 이용한 깊이 우선 탐색(DFS) 방식으로 구현할 수 있습니다. 재귀 알고리즘은 세 가지 핵심 요소를 가집니다.

1. 매개변수 및 반환 값: 재귀 함수의 입력과 출력 형태를 정의합니다.
2. 종료 조건: 재귀 호출이 멈춰야 하는 조건을 명확히 합니다.
3. 단일 재귀 로직: 각 단계에서 수행할 작업을 정의합니다.

전위 순회의 경우, 현재 노드의 값을 먼저 추가한 후 왼쪽, 오른쪽 자식 노드에 대해 재귀 호출을 수행합니다.

from typing import List, Optional

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def dfs(node):
            if node is None:
                return
            result.append(node.val)  # 현재 노드 방문
            dfs(node.left)          # 왼쪽 서브트리 탐색
            dfs(node.right)         # 오른쪽 서브트리 탐색
            
        dfs(root)
        return result

102. 이진 트리의 레벨 순회

주어진 이진 트리의 루트 노드 root가 있을 때, 노드 값들의 레벨 순회 결과를 반환하는 문제입니다. 레벨 순회는 각 레벨의 노드들을 왼쪽에서 오른쪽으로 순서대로 방문합니다.

예시: 입력: root = [3,9,20,null,null,15,7] 출력: [[3],[9,20],[15,7]]

해결 방법:

큐(Queue) 자료구조를 사용하여 너비 우선 탐색(BFS) 방식으로 구현합니다. 큐의 FIFO(First-In, First-Out) 특성은 레벨별 순회 로직과 잘 맞습니다.

각 레벨을 처리할 때, 해당 레벨의 노드 수를 미리 파악하여 for 루프를 사용하면, 현재 레벨을 처리하는 동안 큐에 추가되는 다음 레벨의 노드들이 현재 루프의 반복 횟수에 영향을 주지 않습니다.

from collections import deque
from typing import List, Optional

# TreeNode 클래스는 위에 정의되어 있다고 가정합니다.

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
            
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level_nodes = []
            
            for _ in range(level_size):
                current_node = queue.popleft()
                current_level_nodes.append(current_node.val)
                
                if current_node.left:
                    queue.append(current_node.left)
                if current_node.right:
                    queue.append(current_node.right)
            
            result.append(current_level_nodes)
            
        return result

참고: if node is None: 또는 if not node:와 같이 노드가 없는 경우를 확인하는 것이 if node.val == None: 보다 더 올바른 방법입니다.