leetcode: 94. Binary Tree Inorder Traversal

문제링크

풀이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)