[leetcode] 94. Binary Tree Inorder Traversal

kldaji·2022년 9월 8일
0

leetcode

목록 보기
50/56

Recursion

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val order = mutableListOf<Int>()
        
        inorderTraversal(root, order)
        
        return order
    }
    
    fun inorderTraversal(root: TreeNode?, order: MutableList<Int>) {
        if (root == null) return
                
        inorderTraversal(root.left, order)
        order.add(root.`val`)
        inorderTraversal(root.right, order)
    }
}

Stack

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val stack = Stack<TreeNode>()
        val order = mutableListOf<Int>()
        var curr = root
        
        while (curr != null || stack.isNotEmpty()) {
            while (curr != null) {
                stack.push(curr)
                curr = curr.left
            }
            curr = stack.pop()
            order.add(curr.`val`)
            curr = curr.right
        }
        
        return order
    }
}
profile
다양한 관점에서 다양한 방법으로 문제 해결을 지향하는 안드로이드 개발자 입니다.

0개의 댓글