- 题目要求：
思路：
- 构建一个二叉树，节点有以下属性：
self.left = Noneself.right = Noneself.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解法