[leetcode] 94. Binary Tree Inorder Traversal

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
    }
}