Leetcode 2792. 计算足够大的节点数

1.题目基本信息

1.1.题目描述

给定一棵二叉树的根节点 root 和一个整数 k 。如果一个节点满足以下条件，则称其为 足够大 ：

它的子树中 至少 有 k 个节点。

• 它的值 大于 其子树中 至少 k 个节点的值。
• 返回足够大的节点数。

如果 u == v 或者 v 是 u 的祖先，则节点 u 在节点 v 的 子树 中。

1.2.题目地址

https://leetcode.cn/problems/count-nodes-that-are-great-enough/description/

2.解题方法

2.1.解题思路

递归+归并+二分查找

时间复杂度：O(Klog(N))

2.2.解题步骤

第一步，构建维护变量。result维护足够大的节点数

第二步，构建递归函数。递归任务：返回node子树中所有节点值的升序数组的前k个元素子数组；并在递归的过程中进行计数，更新self.result

2.1.递归出口

2.2.对node的左右子节点的递归结果数组进行归并

2.3.将node.val插入arr数组中

2.4.更新结果变量；并返回递归值

第三步，调用递归，返回结果

3.解题代码

Python代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from bisect import bisect_left

class Solution:
    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:
        # 思路：递归+归并+二分查找。时间复杂度：O(Klog(N))
        # 第一步，构建维护变量。result维护足够大的节点数
        self.result = 0
        # 第二步，构建递归函数。递归任务：返回node子树中所有节点值的升序数组的前k个元素子数组；并在递归的过程中进行计数，更新self.result
        def dfs(node:TreeNode) -> list[int]:
            # 2.1.递归出口
            if node is None:
                return []
            # 2.2.对node的左右子节点的递归结果数组进行归并
            leftList, rightList = dfs(node.left), dfs(node.right)
            arr = [0] * (len(leftList) + len(rightList))
            i, j, k1 = 0, 0, 0
            while i < len(leftList) and j < len(rightList):
                if leftList[i] < rightList[j]:
                    arr[k1] = leftList[i]
                    i += 1; k1 += 1
                else:
                    arr[k1] = rightList[j]
                    j += 1; k1 += 1
            while i < len(leftList):
                arr[k1] = leftList[i]
                i += 1; k1 += 1
            while j < len(rightList):
                arr[k1] = rightList[j]
                j += 1; k1 += 1
            # 2.3.将node.val插入arr数组中
            index = bisect_left(arr, node.val)
            arr.insert(index, node.val)
            # 2.4.更新结果变量；并返回递归值
            if len(arr) >= k and arr[k - 1] < node.val:
                self.result += 1
            return arr[:k]
        # 第三步，调用递归，返回结果
        dfs(root)
        return self.result

4.执行结果