leetcode: 94. Binary Tree Inorder Traversal

kldaji·2021년 12월 13일
1

leetcode

목록 보기
6/56

문제링크

풀이1

  • Recursion
class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        root ?: return listOf<Int>()
        
        val list = mutableListOf<Int>()
        list.addAll(inorderTraversal(root.left))
        list.add(root.`val`)
        list.addAll(inorderTraversal(root.right))
        return list
    }
}

시간복잡도 : O(V)
공간복잡도 : O(V^2)

풀이2

  • Iteration
class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val stack = Stack<TreeNode>()
        val retList = mutableListOf<Int>()
        var curr = root
        while (curr != null || stack.isNotEmpty()) {
            while (curr != null) {
                stack.push(curr)
                curr = curr?.left
            }
            curr = stack.pop()
            retList.add(curr.`val`)
            curr = curr?.right
        }
        return retList
    }
}

시간복잡도 : O(V)
공간복잡도 : O(V)

profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.

0개의 댓글