- 题目要求：
-
思路：
- 构建一个二叉树，节点有以下属性：
-
self.left = None self.right = None self.val = val # 节点值 self.nodecount = 1 # 以后节点值呈现了多少次 self.leftcount = 0 # 左子树节点数量 - 从后往前遍历数组元素，如果以后的数组元素值与以后树节点值相等，那么把以后节点呈现的次数加一
- 如果以后元素的值大于树节点的值，如果以后节点有右节点，持续比拟右节点，如果以后节点没有右节点，用以后的数组元素创立新的节点，插入到树中
- 如果以后元素的值小于节点的值，如果以后节点有左节点，持续比拟左节点，如果以后的节点没有左节点，用以后的数组元素创立新的节点，插入到树中
- 代码：
class TreeNode(object):
def __init__(self, val):
self.left = None
self.right = None
self.val = val # 节点值
self.nodecount = 1 # 以后节点值呈现了多少次
self.leftcount = 0 # 左子树节点数量
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
if n == 0 or n == 1:
return res
root = TreeNode(nums[-1])
for i in range(n - 2, -1, -1):
res[i] = self.insertNode(root, nums[i])
return res
# 往二叉搜寻树中插入新的节点
def insertNode(self, root, val):
cur = root
res = 0
while cur:
if cur.val == val:
cur.nodecount += 1
res += cur.leftcount
break
elif cur.val < val:
res += cur.leftcount + cur.nodecount
if cur.right:
cur = cur.right
else:
cur.right = TreeNode(val)
break
else:
cur.leftcount += 1
if cur.left:
cur = cur.left
else:
cur.left = TreeNode(val)
break
return res- 残缺代码：
class TreeNode(object):
def __init__(self, val):
self.left = None
self.right = None
self.val = val
self.nodecount = 1
self.leftcount = 0
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0] * n
if n == 0 or n == 1:
return res
root = TreeNode(nums[-1])
for i in range(n - 2, -1, -1):
res[i] = self.insertNode(root, nums[i])
return res
def insertNode(self, root, val):
cur = root
res = 0
while cur:
if cur.val == val:
cur.nodecount += 1
res += cur.leftcount
break
elif cur.val < val:
res += cur.leftcount + cur.nodecount
if cur.right:
cur = cur.right
else:
cur.right = TreeNode(val)
break
else:
cur.leftcount += 1
if cur.left:
cur = cur.left
else:
cur.left = TreeNode(val)
break
return res- 参考视频：LeetCode315 计算右侧小于以后元素的个数 BST 解法