LeetCode 94(Binary Tree Inorder Traversal, Python)

1. 문제 링크

• Binary Tree Inorder Traversal - LeetCode

Binary Tree Inorder Traversal - LeetCode

2. 문제 설명

• 이진 트리가 주어졌을 때 중위 순회(inorder traversal)한 결과를 리스트에 담아 반환하는 문제
• 중위 순회가 무엇인지는 5. 배운 점에서 자세히 설명
• 트리 구조에서는 재귀 함수를 자주 사용하게 됨. 트리 구조 문제가 많기 때문에 트리라는 녀석과 재귀 함수에 익숙해져야함. 

3. 처음 풀이

• 트리 끝까지 가서 노드가 None이면 빈 리스트 [] 를 반환
• 노드가 None이 아니라면 중위 순회 정의대로 왼쪽 서브트리를 중위 순회한 후, 루트 노드 방문, 오른쪽 서브트리를 중위 순회한다. 
• 따라서 root.left에 재귀함수 결과값, root.val, root.right에 재귀함수 결과값을 순서대로 result 리스트에 추가하기를 반복

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def find(root):
            result = []
            if root == None: #끝까지 내려가서 None이 나오면 result에 아무것도 추가하지 않기 위해 [] 반환
                return []
            result += find(root.left) #재귀: 왼쪽 서브 트리 중위 순회한 결과를 result에 추가
            result.append(root.val) #루트 노드 값 추가
            result += find(root.right) #재귀: 오른쪽 서브 트리 중위 순회한 결과를 result에 추가
            return result
        return find(root)

4. 다른 풀이

• 이 문제의 경우 조금씩 다를 순 있지만 큰 논리 흐름이나 쓰이는 툴이 대부분 비슷함. 

5. 배운 점

• 트리 자료구조의 노드를 순회하는 방법들
  1. 전위 순회(Preorder Traversal):
     • 루트 노드를 먼저 방문하고, 그 다음에 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회합니다.
     • 방문 순서: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  2. 중위 순회(Inorder Traversal):
     • 왼쪽 서브트리를 중위 순회한 뒤에 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 중위 순회합니다.
     • 방문 순서: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
  3. 후위 순회(Postorder Traversal):
     • 왼쪽 서브트리를 후위 순회한 뒤에 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 방문합니다.
     • 방문 순서: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
  4. 레벨 순회(Level Order Traversal):
     • 각 레벨 순서대로 노드를 방문합니다. 즉, 루트에서부터 각 레벨의 왼쪽에서 오른쪽 순서대로 노드를 방문합니다.

       A
      / \
     B   C
    / \
   D   E
#전위 순회: A -> B -> D -> E -> C
#중위 순회: D -> B -> E -> A -> C
#후위 순회: D -> E -> B -> C -> A
#레벨 순회: A -> B -> C -> D -> E