bài này rating 1739 mà backtrack thì lỏ thật
xem rating như nào vậy bác:v bài hôm nay em không nhìn constrain, nghĩ cả ngày méo ra cách nào ngoài backtrack. Code xong soi Editor thì chỉ có backtrack thật
class Solution:
def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
q, heap = deque([root]), []
while q:
n = len(q)
curr = 0
for _ in range(n):
node = q.popleft()
if node != None:
curr += node.val
q.append(node.left)
q.append(node.right)
heapq.heappush(heap, -curr)
result = 0
if k >= len(heap):
return -1
while k > 0:
result = -heapq.heappop(heap)
k -= 1
return result
class Solution {
public:
long long kthLargestLevelSum(TreeNode* root, int k) {
long long largest = 0;
queue<TreeNode*> q;
q.push(root);
priority_queue<long long> sums;
while (!q.empty()) {
long long sum = calculate(q);
sums.push(sum);
}
if (k > sums.size()) return -1;
for (int i = 0; i < k - 1; ++i) {
sums.pop();
}
return sums.top();
}
long long calculate(queue<TreeNode*>& q) {
queue<TreeNode*> q2;
long long sum = 0;
while (!q.empty()) {
auto node = q.front();
q.pop();
sum += node->val;
if (node->left)
q2.push(node->left);
if (node->right)
q2.push(node->right);
}
q.swap(q2);
return sum;
}
};
function kthLargestLevelSum(root: TreeNode | null, k: number): number {
const arr: TreeNode[] = [];
const nums: number[] = [];
arr.push(root);
while(arr.length) {
let size = arr.length, res = 0;
for (let i = 0; i < size; i++) {
const node = arr.shift();
res+= node.val;
if (node.left) arr.push(node.left);
if (node.right) arr.push(node.right);
}
nums.push(res)
}
if (nums.length < k) return -1;
nums.sort((a,b) => b-a);
return nums[k-1]
};Cái rating này cũng tương đối thôi, ko hiểu nó dựa vào đâu để đánh giá, mấy bài đồ thị raing 2k 2k1 mà ko khó lắm, trong khi mấy bài greedy 1k7 1k8 khó lòi cả mắt. Bỏ đi tập trung vào làm đề thôi.:v bài hôm nay em không nhìn constrain, nghĩ cả ngày méo ra cách nào ngoài backtrack. Code xong soi Editor thì chỉ có backtrack thật
class Solution {
public:
long long kthLargestLevelSum(TreeNode* root, int k) {
queue<TreeNode*> q;
q.push(root);
priority_queue<long long> pq;
while (!q.empty()) {
long long sum = 0;
int size = q.size();
while (size--) {
TreeNode* tmp = q.front();
q.pop();
sum += tmp->val;
if (tmp->left != nullptr) q.push(tmp->left);
if (tmp->right != nullptr) q.push(tmp->right);
}
pq.push(sum);
}
long long ans;
if (pq.size() < k) return -1;
while(k--) {
ans = pq.top();
pq.pop();
}
return ans;
}
};
# 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
class Solution:
def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
heap = []
queue = deque()
queue.append(root)
while queue:
size = len(queue)
levelSum = 0
for i in range(size):
item = queue.popleft()
levelSum += item.val
if item.left:
queue.append(item.left)
if item.right:
queue.append(item.right)
heapq.heappush(heap, levelSum)
if len(heap) > k:
heapq.heappop(heap)
return -1 if len(heap) < k else heap[0]
# Definition for a binary tree node.
# 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
class Solution:
def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
queue = [root]
level_sum = []
while queue:
sum = 0
children = []
for v in queue:
sum += v.val
if v.left:
children.append(v.left)
if v.right:
children.append(v.right)
level_sum.append(sum)
queue = children
level_sum.sort(reverse=True)
if len(level_sum) < k:
return -1
return level_sum[k-1]Xử lý heap mượt quá anh ơi, luôn giữ heap chỉ có k slot thôi thì thằng top sẽ là thằng độ lớn thứ kth luôn
/**
* 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:
void dfs(TreeNode* cur, vector<long long>& level_sums, int level, int& max_level) {
level_sums[level] += cur->val;
max_level = max(max_level, level);
if (cur->left != nullptr) dfs(cur->left, level_sums, level + 1, max_level);
if (cur->right != nullptr) dfs(cur->right, level_sums, level + 1, max_level);
}
long long kthLargestLevelSum(TreeNode* root, int k) {
if (root == nullptr) return -1;
vector<long long> level_sums(1e5+5);
int max_level = 0;
dfs(root, level_sums, 0, max_level);
// cout << max_level << " " << k << "\n";
if (max_level + 1 < k) return -1;
sort(level_sums.begin(), level_sums.end(), std::greater<>());
return level_sums[k-1];
// return 0;
}
};Top kth largest thì dùng min heap, top kth smalest thì dùng max heap là ngon đó fence, muốn nhanh hơn để đấm interviewer thì viết 1 cái quick select nữa để viết thành O(n) nhưng worst case là 0(n^2)Xử lý heap mượt quá anh ơi, luôn giữ heap chỉ có k slot thôi thì thằng top sẽ là thằng độ lớn thứ kth luôn
Em cũng mới thấy cách O(n) là quick select xong, để tối về lại thẩm tiếp cách đấy vậy. Nhưng mà cảm ơn anh vì cái pattern kth largest dùng min heap và kth smallest dùng max heap ạ
.
class Solution {
public long kthLargestLevelSum(TreeNode root, int k) {
Queue<TreeNode> queue = new LinkedList();
PriorityQueue<Long> sums = new PriorityQueue<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
long curLevelSum =0 ;
TreeNode node = new TreeNode();
while(size-->0){
node = queue.poll();
curLevelSum+= node.val;
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
sums.offer(curLevelSum);
if(sums.size()>k){
sums.poll();
}
}
return sums.size()<k?-1:sums.peek();
}
}cái lày trong này xài suốt ý mà. làm daily nguyên năm chăm đi cop sol mấy bác phi đôm với anold, nchhxyz kiểu gì cũng chôm dc thôiEm cũng mới thấy cách O(n) là quick select xong, để tối về lại thẩm tiếp cách đấy vậy. Nhưng mà cảm ơn anh vì cái pattern kth largest dùng min heap và kth smallest dùng max heap ạ
có 2 cách, cài extension chrome hoặc cop tên bài bỏ vào trang CLIST ...
k nó là input nên tính theo logk.nếu k max là n thì TC có tính là O(nlogn) ko mấy fency. Hay vẫn coi là O(n + nlogk)
k nó là 1 input riêng, ko bị phụ thuộc vào n. thì tính độ phức tạp là nlogk thôi. mình nghĩ như v
