Share my Accepted Ruby Solution


  • 1
    def kth_smallest(root, k)
        stack,ans = [[false,root]], []
        while not stack.empty?
            visit, node = stack.pop
            if node
                if visit
                   ans << node.val
                   return ans[-1] if ans.length == k
                else
                    stack << [false,node.right] << [true,node] << [false,node.left]
                end
            end
        end
    end

  • 0

    Thanks, I'm a Ruby beginner and like seeing Ruby solutions :-). Given previous nice surprises, I correctly guessed that it can pop several elements at once, so I rewrote it a bit to do that. Not sure it's better.

    def kth_smallest(root, k)
        stack,ans = [false,root], []
        while not stack.empty?
            visit, node = stack.pop 2
            if node
                if visit
                   ans << node.val
                   return ans[-1] if ans.length == k
                else
                    stack.push false,node.right, true,node, false,node.left
                end
            end
        end
    end
    

    Or storing "pairs", but only for the cases with true (and making visit the second element, so popping a non-pair makes it nil, which is falsey, so an explicit false isn't necessary).

    def kth_smallest(root, k)
        stack,ans = [root], []
        while not stack.empty?
            node, visit = stack.pop
            if node
                if visit
                   ans << node.val
                   return ans[-1] if ans.length == k
                else
                    stack << node.right << [node, true] << node.left
                end
            end
        end
    end

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.