LeetCode 145(Binary Tree Postorder Traversal, Python)

1. 문제 링크

• Binary Tree Postorder Traversal - LeetCode

Binary Tree Postorder Traversal - LeetCode

2. 문제 설명

• 트리 순회 위키피디아 트리 순회 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
• 주어진 트리를 후위 순회한 결과를 리스트로 반환할 것
• 전위 순회(preorder traversal)
  • 부모 → 왼쪽 서브 트리 → 오른쪽 서브 트리
• 중위 순회(inorder traversal)
  • 왼쪽 서브 트리 → 부모 → 오른쪽 서브 트리
• 후위 순회(postorder traversal)
  • 왼쪽 서브 트리 → 오른쪽 서브 트리 → 부모

3. 풀이

• 재귀 함수 사용
• node가 None이면 [] 반환
• None 아니면 왼쪽 서브 트리와 오른쪽 서브 트리에 재귀 함수 걸어 결과를 더한 후 root.val을 리스트에 넣는 것을 반복

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]

4. 배운 점

• 이진 트리를 순회하는 방법들
  • 전위 순회(Preorder Traversal):
    • 루트 노드를 먼저 방문하고, 그 다음에 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회합니다.
    • 방문 순서: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
  • 중위 순회(Inorder Traversal):
    • 왼쪽 서브트리를 중위 순회한 뒤에 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 중위 순회합니다.
    • 방문 순서: 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
  • 후위 순회(Postorder Traversal):
  • 왼쪽 서브트리를 후위 순회한 뒤에 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 방문합니다.
  • 방문 순서: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
• 레벨 순회(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