Leetcode315-计算右侧小于当前元素的个数-Python实现

1次阅读

共计 1596 个字符，预计需要花费 4 分钟才能阅读完成。

题目要求：

思路：
- 构建一个二叉树，节点有以下属性：
- ```
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