层序遍历+小根堆，LeetCode 2476. 二叉搜索树最近节点查询

本文主要是介绍层序遍历+小根堆，LeetCode 2476. 二叉搜索树最近节点查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

给你一棵二叉树的根节点 root 和一个正整数 k 。

树中的层和是指 同一层 上节点值的总和。

返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。

注意，如果两个节点与根节点的距离相同，则认为它们在同一层。

2、接口描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:long long kthLargestLevelSum(TreeNode* root, int k) {}
};

3、原题链接

2583. 二叉树中的第 K 大层和

二、解题报告

1、思路分析

换汤不换药，在层序遍历的基础上，用堆维护前K大元素元素

层数够k层的话就返回堆顶

2、复杂度

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

3、代码详解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:
TreeNode* q[100005];
int f, b;long long kthLargestLevelSum(TreeNode* root, int k) {priority_queue<long long, vector<long long>, greater<long long>> pq;f = b = 0, q[b++] = root;while(b - f){long long s = 0;for(int r = b; f < r; ){s += (root = q[f++]) -> val;if(root -> left) q[b++] = root -> left;if(root -> right) q[b++] = root -> right;}pq.emplace(s);if(pq.size() > k)   pq.pop();}if(pq.size() < k) return -1;return pq.top();}
};

这篇关于层序遍历+小根堆，LeetCode 2476. 二叉搜索树最近节点查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！