Python inorder traversal, O(N) time.


  • 0
    A
    class Solution:
    # @param {TreeNode} root
    # @param {integer} k
    # @return {integer}
    def kthSmallest(self, root, k):
        self.ans = None
        self.n = 0
        self.inorder(root, k)
        return self.ans
    
    def inorder(self, root, k):
        if root == None:
            return
        if self.n >= k:
            return
        self.inorder(root.left, k)
        self.n += 1
        if self.n == k:
            self.ans = root.val
            return
        self.inorder(root.right, k)

Log in to reply
 

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