Python inorder with cache o(n) for first time


  • 1
    L

    class Solution(object):
    def kthSmallest(self, root, k):
    """
    :type root: TreeNode
    :type k: int
    :rtype: int
    """
    a=[]
    def inorder(root,a):
    if root is None:
    return
    inorder(root.left,a)
    a.append(root.val)
    inorder(root.right,a)
    return a
    return a[k] if root.val in a else inorder(root,a)[k-1]


  • 0
    B

    I used a the same idea as you. Here is my solution.

    class Solution(object):
        def kthSmallest(self, root, k):
            order = []
            def inorder(node):
                if node:
                    inorder(node.left)
                    order.append(node.val)
                    if len(order) == k: 
                        return
                    inorder(node.right)
            inorder(root)
            return order[k-1]
    

Log in to reply
 

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