[leetcode 94] Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal

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

해결 과정

Tree Inorder Traversal 는 왼쪽->루트->오른쪽 순서로 순회하는 것이다. result 값을 저장 할 파라미터를 받는 별도의 메소드를 만들고, 루트 순회 순서에 해당 값을 result 리스트에 추가해주었다.

코드

fun inorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    inorder(result, root)
    return result
}
    
fun inorder(result: MutableList<Int>, root: TreeNode?)  {
    root?.let {
        it.left?.let { left  ->
            inorder(result, left)
        }
        result.add(it.`val`)  
        it.right?.let { right ->
            inorder(result, right)
        }
    }
}

배운 점

• Stack을 활용해서도 풀 수 있다.

fun inorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    val stack = Stack<TreeNode>()
    val curr = root

    while(null != curr || stack.isNotEmpty()) {
        while(null != curr) {
            stack.push(curr)
            curr = current.left
        }
        curr = stack.pop()
        result.add(curr.`val`)
        curr = curr.right
    }
    return result
}