def countSmaller(self, nums):
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.count = 0
def bst_insert(root, val, result, count):
if not root:
root = Node(val)
result.append(count)
return root
if val > root.val:
root.right = bst_insert(root.right, val, result, root.count + 1 + count)
else:
root.count += 1
root.left = bst_insert(root.left, val, result, count)
return root
root = None
result = []
for num in reversed(nums):
if not root:
root = Node(num)
result.append(0)
else:
bst_insert(root, num, result, 0)
return result[::-1]
CmRlZiBjb3VudFNtYWxsZXIoc2VsZiwgbnVtcyk6CiAgICBjbGFzcyBOb2RlOgogICAgICAgIGRlZiBfX2luaXRfXyhzZWxmLCB2YWwpOgogICAgICAgICAgICBzZWxmLnZhbCA9IHZhbAogICAgICAgICAgICBzZWxmLmxlZnQgPSBOb25lCiAgICAgICAgICAgIHNlbGYucmlnaHQgPSBOb25lCiAgICAgICAgICAgIHNlbGYuY291bnQgPSAwCgogICAgZGVmIGJzdF9pbnNlcnQocm9vdCwgdmFsLCByZXN1bHQsIGNvdW50KToKICAgICAgICBpZiBub3Qgcm9vdDoKICAgICAgICAgICAgcm9vdCA9IE5vZGUodmFsKQogICAgICAgICAgICByZXN1bHQuYXBwZW5kKGNvdW50KQogICAgICAgICAgICByZXR1cm4gcm9vdAogICAgICAgIGlmIHZhbCA+IHJvb3QudmFsOgogICAgICAgICAgICByb290LnJpZ2h0ID0gYnN0X2luc2VydChyb290LnJpZ2h0LCB2YWwsIHJlc3VsdCwgcm9vdC5jb3VudCArIDEgKyBjb3VudCkKICAgICAgICBlbHNlOgogICAgICAgICAgICByb290LmNvdW50ICs9IDEKICAgICAgICAgICAgcm9vdC5sZWZ0ID0gYnN0X2luc2VydChyb290LmxlZnQsIHZhbCwgcmVzdWx0LCBjb3VudCkKICAgICAgICByZXR1cm4gcm9vdAoKICAgIHJvb3QgPSBOb25lCiAgICByZXN1bHQgPSBbXQogICAgZm9yIG51bSBpbiByZXZlcnNlZChudW1zKToKICAgICAgICBpZiBub3Qgcm9vdDoKICAgICAgICAgICAgcm9vdCA9IE5vZGUobnVtKQogICAgICAgICAgICByZXN1bHQuYXBwZW5kKDApCiAgICAgICAgZWxzZToKICAgICAgICAgICAgYnN0X2luc2VydChyb290LCBudW0sIHJlc3VsdCwgMCkKICAgIHJldHVybiByZXN1bHRbOjotMV0=