[Leetcode - Swift] 94. Binary Tree Inorder Traversal

문제

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Binary Tree Inorder Traversal - LeetCode

 

풀이

이진 트리의 순회 방법에는 레벨, 전위, 중위, 후위 순회가 있다.

레벨 순회는 BFS로 구현할 수 있고, 전위, 중위, 후위 순회는 DFS로 구현할 수 있다.

 

👉🏼 방문 순서

전위 순회 : root -> left -> right

중위 순회 : left -> root -> right

후위 순회 : left -> right -> root

 

나는 DFS로 중위 순회를 구현하였고, 재귀를 활용하였다.

처음 생각해낸 풀이로는, 맨 끝에 도달하게 되는 base case로 빈 배열의 타입을 반환한다는 게 이해가 잘 안가서, Int 타입을 반환하는 새로운 함수 dfs를 구현해주었고, 이 dfs 함수를 재귀적으로 호출해주었다.

하지만 다른 풀이를 참고하니, 배열에 배열을 더해주기 때문에 괜찮다는 것을 알게 되었다. 그래서 본 함수를 재귀로 구현해주었다.

 

코드

import Foundation

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var visited = [Int]()
        func dfs(_ current: TreeNode?) {
            if let current = current {
                dfs(current.left)
                visited.append(current.val)
                dfs(current.right)
            } else {
                return
            }
        }
        dfs(root)
        return visited
    }
}

class Solution2 {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let current = root else { return [] }
        return inorderTraversal(root?.left) + [current.val] + inorderTraversal(current.right)
    }
}