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
        if k==(ncount+1):
            return root.val
        elif k<=ncount:
            return self.kthSmallest(root.left,k)
            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.