Share my python code with recursive solution,with explanation


  • 0
    class Solution(object):
    def nsize(self,root):
        if not root:return 0
        return 1+self.nsize(root.left)+self.nsize(root.right)
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        if not root:return 0
        ncount=self.nsize(root.left)
        if k==(ncount+1):
            return root.val
        elif k<=ncount:
            return self.kthSmallest(root.left,k)
        else:
            return self.kthSmallest(root.right,k-ncount-1)
    

    Firstly, we count the size of the left tree(ncount),if ncount>=k,then search the kth smallest element in left tree, if ncount+1=k,then the root is the kth smallest element, otherwise, we need to search the (k-ucount-1)th element in the right tree.


Log in to reply
 

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