Binary Tree - Inorder, Postorder, Preorder 코드 구조

 

DFS base Post-order, Pre-order, In-order 구조

 

 

 

Preorder, Inorder, Postorder 의 구조는 전체적으로 흡사하지만

어디서 어떻게 재귀함수를 호출하느냐 차이이다.

크게 root, left, right 구조로 나뉘어지고

 

root 를 제일 먼저 호출하는건 Preorder

root 를 가운데서 호출하는건 Inorder

root를 맨 마지막에 호출하는건 Postorder

 

여기서 'root를 호출하다'의 의미는

해당 Node 그 자신을 의미하며

코드의 목적에 따라

조건절이 들어가도 되는 부분을 의미한다.

 

 

---

 

DFS 코드 구조

Nodes = []

def preorder(node):
    if node is None:
        return
    Nodes.append(node.val)
    preorder(node.left)
    preorder(node.right)
    
def inorder(node):
    if node is None:
        return
    inorder(node.left)
    Nodes.append(node.val)
    inorder(node.right)
    
def postorder(node):
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    Nodes.append(node.val)

 

 

 

종료조건 - return

재귀함수 호출 - inorder 가장 왼쪽의 값

list에 해당값 append

재귀함수 호출 - inorder 가장 오른쪽 

 

풀고자 하는 목적에 따라 append 부분의 조건을 변형할 수 있음.

 

 

DFS, BFS 문제들이 거의 필수 항목으로 빅테크 인터뷰에서

다뤄지는데, 해당 구조만 기억하고 알면

나머지는 응용해서 풀면 된다.

 

 

---

 

BFS 코드 구조

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    levels = []
    if root is None:
        return levels

    level = 0
    queue = deque([root,])
    while queue:
        levels.append([])
        length = len(queue)
        for i in range(length):
            node = queue.popleft()
            levels[level].append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        level += 1
    return levels

 

 

 

BFS 는 dequeue를 이용해 풀면 아주 쉽다.

위의 코드는 Leetcode 98번

문제를 BFS 방식으로 푼 풀이이다.

 

1. deque 정의

2. root 를 deque 에 삽입

3. 문제에 따른 조건 수행

4. node.left 부분 apend

5. node.right 부분 append

 

 

 

---

<정리>

DFS - recursion 을 사용한 풀이

    - Preorder, Inorder, Postorder 는 node itself 를 어디에 추가하느냐의 차이

BFS - dequeue를 사용한 풀이

    - left 부분 append

    - right 부분 append