二叉搜索树染色

难度: Medium

欢迎各位勇者来到力扣城，本次试炼主题为「二叉搜索树染色」。每位勇士面前设有一个**二叉搜索树**的模型，模型的根节点为 `root`，树上的各个节点值均不重复。初始时，所有节点均为蓝色。现在按顺序对这棵二叉树进行若干次操作， `ops[i] = [type, x, y]` 表示第 `i` 次操作为： + `type` 等于 0 时，将节点值范围在 `[x, y]` 的节点均染蓝 + `type` 等于 1 时，将节点值范围在 `[x, y]` 的节点均染红请返回完成所有染色后，该二叉树中红色节点的数量。 **注意：** + 题目保证对于每个操作的 `x`、`y` 值定出现在二叉搜索树节点中 **示例 1：** >输入：`root = [1,null,2,null,3,null,4,null,5], ops = [[1,2,4],[1,1,3],[0,3,5]]` > >输出：`2` > >解释： >第 0 次操作，将值为 2、3、4 的节点染红； >第 1 次操作，将值为 1、2、3 的节点染红； >第 2 次操作，将值为 3、4、5 的节点染蓝； >因此，最终值为 1、2 的节点为红色节点，返回数量 2 ![image.png](https://pic.leetcode-cn.com/1649833948-arSlXd-image.png){:width=230px} **示例 2：** >输入：`root = [4,2,7,1,null,5,null,null,null,null,6]` >`ops = [[0,2,2],[1,1,5],[0,4,5],[1,5,7]]` > >输出：`5` > >解释： >第 0 次操作，将值为 2 的节点染蓝； >第 1 次操作，将值为 1、2、4、5 的节点染红； >第 2 次操作，将值为 4、5 的节点染蓝； >第 3 次操作，将值为 5、6、7 的节点染红； >因此，最终值为 1、2、5、6、7 的节点为红色节点，返回数量 5 ![image.png](https://pic.leetcode-cn.com/1649833763-BljEbP-image.png){:width=230px} **提示：** + `1 <= 二叉树节点数量 <= 10^5` + `1 <= ops.length <= 10^5` + `ops[i].length == 3` + `ops[i][0]` 仅为 `0` or `1` + `0 <= ops[i][1] <= ops[i][2] <= 10^9` + `0 <= 节点值 <= 10^9`

Submission

运行时间: 345 ms

内存: 67.8 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        values = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            values.append(root.val)
            dfs(root.right)
        
        dfs(root)
        
        ans = 0
        for tp, x, y in ops[::-1]:
            i = bisect.bisect_left(values, x)
            j = bisect.bisect_right(values, y)
            if tp == 1:
                ans += j-i
            values = values[:i] + values[j:]
            if not values:
                break
        return ans

Explain

此题解通过首先将二叉搜索树的所有节点值收集到一个列表中，然后逆序遍历给定的操作列表。对于每个操作，它使用二分搜索确定操作影响的值范围在列表中的位置，然后根据操作类型更新红色节点的计数器。操作完成后，对列表进行切片以删除已处理的值范围。该方法利用了二叉搜索树的有序性和二分搜索来有效处理节点范围。

时间复杂度: O(m log n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getNumber(self, root: Optional[TreeNode], ops: List[List[int]]) -> int:
        values = []
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            values.append(root.val)  # Collect node values in sorted order
            dfs(root.right)
        
        dfs(root)
        
        ans = 0
        for tp, x, y in ops[::-1]:
            i = bisect.bisect_left(values, x)
            j = bisect.bisect_right(values, y)
            if tp == 1:
                ans += j-i  # Count the nodes to be painted red
            values = values[:i] + values[j:]  # Remove the range of values affected by the operation
            if not values:
                break
        return ans

Explore

题解中选择逆序遍历操作列表的原因是为了确保在处理每个操作时，操作影响的节点范围不会被后续的操作影响。如果从后向前应用操作，可以避免在删除或修改节点值范围时对未来操作产生影响。这种方法允许我们在处理每个操作时，只考虑当前操作的影响，而不需要担心后续操作可能对已处理的节点范围造成的干扰。

在逆序遍历操作列表时，直接移除已处理的值范围不会影响后续操作的正确性。由于我们是从操作列表的最后一个操作开始处理，并且每次处理都是针对当前状态下的值范围，所以一旦一个范围被处理（例如染色或计数），它就不再需要被后续的操作考虑。这种方法确保了每个操作都是在一个更新后的环境中独立执行，从而避免了对未来操作的干扰。

题解中使用深度优先搜索（DFS）来收集所有节点值，确实会得到一个有序的列表。这是因为在二叉搜索树（BST）中，如果按照中序遍历（即先遍历左子树，然后访问根节点，最后遍历右子树）的方式进行，遍历得到的值序列是按照从小到大的顺序排列的。因此，DFS在此处确保了值的有序性，这是利用二叉搜索树的性质得到的结果。