이진 트리 유형 (DFS)

이 유형을 파악하기 전에 이진 트리가 무엇인지, 코드에서 어떻게 표현되고 있는지, 그리고 재귀에 대해서 잘 이해하고 있는지를 체크해보세요

 

오늘은 이진 트리를 순회하는 방법에 대해 알아볼 것입니다. 트리를 순회하는 것은 트리 내의 요소에 접근하는 방법이고, 이는 트리 관련 문제를 해결하는데에 있어 필수적입니다.

 

기존 LinkedList에서의 요소 순회

func getSum(_ head: ListNode?) -> Int {
    var ans = 0
    var current = head
    
    while current != nil {
        ans += current!.val
        current!.next
    }
    
    return ans
}

 

• head부터 시작하여 연결 리스트의 모든 합을 찾기 위해 각 노드에 접근함
• .next 프로퍼티를 이용하여 노드를 순회하는데, 이진 트리를 순회하는 것도 유사함
  • root에서 시작하여 자식 포인터인 .left와 .right를 사용하여 순회함
• 연결 리스트는 반복문을 사용했지만, 이진 트리는 재귀를 사용함

 

트리의 순회 방법에는 2가지 주요 유형이 있습니다.

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

오늘은 DFS에 대해서 알아볼 것이고, DFS를 수행하는 방법에도 3가지가 있습니다.

• 전위 (preorder)
• 중위 (inorder)
• 후위 (postorder)

 

Depth-first search (DFS)

참고: 노드의 깊이는 루트로부터의 거리

 

DFS에서는 한 방향을 잡고, 트리의 리프 노드까지 도달한 후, 다른 방향으로 이동을 합니다.

예를 들어, 왼쪽 방향으로 우선 순위를 둘 경우, node.left를 사용하여 왼쪽 서브 트리를 완전히 탐색할 때까지 이동합니다. 그 다음 오른쪽 서브트리를 탐색합니다.

func dfs(_ node: TreeNode?) {
    guard let node = node else {
        return
    }
    
    dfs(node.left)
    dfs(node.right)
}

 

• 여기서 중요한 점은 각 dfs 함수의 호출이 각자의 버전을 가지고 있다는 것을 인지해야 합니다.
• 즉, 재귀 함수에서 각 함수는 독립적인 로컬 스코프를 가지고 있다는 것을 이해해야 함

 

DFS 문제 해결

1. node = null와 같은 기본 케이스 처리하기

2. 현재 노드에 대한 로직 수행 (문제마다 다름)

3. 자식 노드 재귀적 탐색

4. 답 반환

 

이진 트리 문제를 해결할 때, 가장 중요한 것은 각 함수 호출이 현재 노드를 루트로 하는 서브트리를 입력으로 받아, 원래 문제를 해결하고 답을 반환하는 동작 방식을 이해하는 것입니다. 

https://leetcode.com/

 

 

전위 순회 (Preorder)

• 자식 노드로 이동하기 전, 현재 노드에 대한 로직을 수행함
• 예를 들어, 트리 내의 각 노드의 값을 출력하고 싶을 경우, 먼저 현재 노드에 대한 값을 출력한 후, 자식 서브 트리를 탐색합니다.

func preorderDFS(_ node: TreeNode?) {
    guard let node = node else {
        return 
    } 
    
    print(node.val)
    preorderDFS(node.left)
    preorderDFS(node.right)
}

 

• 위 코드를 실행하면 노드가 다음 순서로 출력됩니다 → 0, 1, 3, 4, 6, 2, 5.
• 각 함수 호출의 시작 부분에서 로직(출력)이 즉시 수행되기 때문에, 전위 순회는 함수 호출이 발생하는 순서대로 노드를 처리합니다.

 

중위 순회 (Preorder)

• 먼저 왼쪽 자식을 재귀적으로 호출한 후, 현재 노드에 대한 로직을 수행하고, 이후 오른쪽 자식을 재귀적으로 호출함
• 왼쪽 자식이 리프 노드에 도달하기 전까지 로직이 수행되지 않음

func inorderDFS(_ node: TreeNode?) {
    guard let node = node else {
        return 
    } 
    
    inorderDFS(node.left)
    print(node.val)
    inorderDFS(node.right)
}

 

• 노드는 다음 순서로 출력됩니다 → 3, 1, 4, 6, 0, 2, 5
• 어떤 노드든 그 값은 왼쪽 서브트리의 모든 값이 출력된 후에야 출력되며, 오른쪽 서브트리의 값들은 그 후에 출력됩니다.

 

후위 순회 (Preorder)

• 먼저 왼쪽과 오른쪽 자식을 재귀적으로 호출한 후, 현재 노드에 대한 로직을 수행함

func postorderDFS(_ node: TreeNode?) {
    guard let node = node else {
        return 
    } 
    
    postorderDFS(node.left)
    postorderDFS(node.right)
    print(node.val)
}

 

• 노드는 다음 순서로 출력됩니다 → 3, 6, 4, 1, 5, 2, 0

 

정리

각 순회의 이름은 현재 노드의 로직이 수행되는 시점에 있음

• pre -> 자식들 전에
• in -> 자식 중간에
• post -> 자식들 후에

 

트리 만들어보기

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

/*
코드는 다음과 같은 트리를 만듭니다
    0
  /   \
 1     2
*/

let root = TreeNode(0)
let one = TreeNode(1)
let two = TreeNode(2)

root.left = one
root.right = two

print(root.left?.val ?? "nil")
print(root.right?.val ?? "nil")

 

 

 

문제 1. 111. Minimum Depth of Binary Tree

• 주어진 이진 트리의 최소 깊이를 구해라!
• 즉, 루트 노드로부터 각 자식에 대한 리프 노드까지의 깊이 중, 가장 최솟값을 구해야하는 문제

 

class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        guard root != nil else { return 0 }
        
        if root?.left != nil && root?.right != nil {
            return min(minDepth(root?.left), minDepth(root?.right)) + 1
        }
        
        if root?.left != nil {
            return minDepth(root?.left) + 1
        }
        
        return minDepth(root?.right) + 1
    }
}

 

 

 

 

Reference

• https://leetcode.com/