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_leftclass Solution:def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:# 思路：递归+归并+二分查找。时间复杂度：O(Klog(N))# 第一步，构建维护变量。result维护足够大的节点数self.result = 0# 第二步，构建递归函数。递归任务：返回node子树中所有节点值的升序数组的前k个元素子数组；并在递归的过程中进行计数，更新self.resultdef 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, 0while i < len(leftList) and j < len(rightList):if leftList[i] < rightList[j]:arr[k1] = leftList[i]i += 1; k1 += 1else:arr[k1] = rightList[j]j += 1; k1 += 1while i < len(leftList):arr[k1] = leftList[i]i += 1; k1 += 1while 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 += 1return arr[:k]# 第三步，调用递归，返回结果dfs(root)return self.result

4.执行结果