Pythonic approach with generator


  • 28
    C

    With generator in python, one very straightforward solution might be:

    class Solution:
        # @param {TreeNode} root
        # @param {integer} k
        # @return {integer}
        def kthSmallest(self, root, k):
            for val in self.inorder(root):
                if k == 1:
                    return val
                else:
                    k -= 1
            
        def inorder(self, root):
            if root is not None:
                for val in self.inorder(root.left):
                    yield val
                yield root.val
                for val in self.inorder(root.right):
                    yield val

  • 2

    Very nice, wish I had thought of that. And I wish we had Python 3 and its yield from. Wrote my own version of it now:

    def kthSmallest(self, root, k):
        def inorder(node):
            if node:
                for val in inorder(node.left):
                    yield val
                yield node.val
                for val in inorder(node.right):
                    yield val
        return next(itertools.islice(inorder(root), k-1, k))
    

  • 0
    X

    Thanks very much for your unbelievable solution.


  • 0
    C

    @clockwise9 brilliant use of yield


  • 0
    L

    @StefanPochmann Nice solution. I'm not too comfortable with yield yet, but would this technically be a O(1) space solution?


  • 0

    @haxet That would be neat :-). But no. Each of my generators only uses O(1) space, but when I'm at depth d, then I have d nested generators in memory at the same time (one for each level, and their combined state reflect the path to the current node).


  • 0
    P
    This post is deleted!

  • 1

    @pyqt Not sure what to explain, it's just inorder traversal and taking the kth element. But here's the yield from version:

    def kthSmallest(self, root, k):
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        return next(itertools.islice(inorder(root), k-1, k))

  • 0
    M

    Excellent Solution!!


Log in to reply
 

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