Posts published in “Tree”

花花酱 LeetCode 3319. K-th Largest Perfect Subtree Size in Binary Tree

By zxi on October 12, 2024

You are given the root of a binary tree and an integer k.

Return an integer denoting the size of the k^th largest perfect binary

subtree, or -1 if it doesn’t exist.

A perfect binary tree is a tree where all leaves are on the same level, and every parent has two children.

Example 1:

Input: root = [5,3,6,5,2,5,7,1,8,null,null,6,8], k = 2

Output: 3

Explanation:

The roots of the perfect binary subtrees are highlighted in black. Their sizes, in decreasing order are [3, 3, 1, 1, 1, 1, 1, 1].
The 2^nd largest size is 3.

Example 2:

Input: root = [1,2,3,4,5,6,7], k = 1

Output: 7

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [7, 3, 3, 1, 1, 1, 1]. The size of the largest perfect binary subtree is 7.

Example 3:

Input: root = [1,2,3,null,4], k = 3

Output: -1

Explanation:

The sizes of the perfect binary subtrees in decreasing order are [1, 1]. There are fewer than 3 perfect binary subtrees.

Constraints:

The number of nodes in the tree is in the range [1, 2000].
1 <= Node.val <= 2000
1 <= k <= 1024

Solution: DFS

Write a function f() to return the perfect subtree size at node n.

def f(TreeNode n):
if not n: return 0
l, r = f(n.left), f(n.right)
return l + r + 1 if l == r && l != -1 else -1

Time complexity: O(n + KlogK)
Space complexity: O(n)

class Solution {

public:

int kthLargestPerfectSubtree(TreeNode* root, int k) {

vector<int> ss;

function<int(TreeNode*)> PerfectSubtree = [&](TreeNode* node) -> int {

if (node == nullptr) return 0;

int l = PerfectSubtree(node->left);

int r = PerfectSubtree(node->right);

if (l == r && l != -1) {

ss.push_back(l + r + 1);

return ss.back();

}

return -1;

};

PerfectSubtree(root);

sort(rbegin(ss), rend(ss));

return k <= ss.size() ? ss[k - 1] : -1;

}

};

花花酱 LeetCode 2583. Kth Largest Sum in a Binary Tree

By zxi on March 5, 2023

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2^nd largest level sum is 13.

Example 2:

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= 10⁶
1 <= k <= n

Solution: DFS + Sorting

Use DFS to traverse the tree and accumulate level sum. Once done, sort the level sums and find the k-th largest one.

Time complexity: O(n)
Space complexity: O(n)

Note: sum can be very large, use long long.

C++

// Author: Huahua

class Solution {

public:

long long kthLargestLevelSum(TreeNode* root, int k) {

vector<long long> sums;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

while (d >= sums.size()) sums.push_back(0);

sums[d] += root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

if (sums.size() < k) return -1;

sort(rbegin(sums), rend(sums));

return sums[k - 1];

}

};

花花酱 LeetCode 2416. Sum of Prefix Scores of Strings

By zxi on September 18, 2022

You are given an array words of size n consisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].

For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".

Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Note that a string is considered as a prefix of itself.

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists of lowercase English letters.

Solution: Trie

Insert all the words into a tire whose node val is the number of substrings that have the current prefix.

During query time, sum up the values along the prefix path.

Time complexity: O(sum(len(word))
Space complexity: O(sum(len(word))

C++

// Author: Huahua

struct Trie {

Trie* ch[26] = {};

int cnt = 0;

void insert(string_view s) {

Trie* cur = this;

for (char c : s) {

if (!cur->ch[c - 'a'])

cur->ch[c - 'a'] = new Trie();

cur = cur->ch[c - 'a'];

++cur->cnt;

}

int query(string_view s) {

Trie* cur = this;

int ans = 0;

for (char c : s) {

cur = cur->ch[c - 'a'];

ans += cur->cnt;

}

return ans;

}

};

class Solution {

public:

vector<int> sumPrefixScores(vector<string>& words) {

Trie* root = new Trie();

for (const string& w : words)

root->insert(w);

vector<int> ans;

for (const string& w : words)

ans.push_back(root->query(w));

return ans;

}

};

花花酱 LeetCode 2265. Count Nodes Equal to Average of Subtree

By zxi on May 10, 2022

Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.

Note:

The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
A subtree of root is a tree consisting of root and all of its descendants.

Example 1:

Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation: 
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.

Example 2:

Input: root = [1]
Output: 1
Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.

Constraints:

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000

Solution: Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua

class Solution {

public:

int averageOfSubtree(TreeNode* root) {

// Returns {sum(val), sum(node), ans}

function<tuple<int, int, int>(TreeNode*)> getSum

= [&](TreeNode* root) -> tuple<int, int, int> {

if (!root) return {0, 0, 0};

auto [lv, lc, la] = getSum(root->left);

auto [rv, rc, ra] = getSum(root->right);

int sum = lv + rv + root->val;

int count = lc + rc + 1;

int ans = la + ra + (root->val == sum / count);

return {sum, count, ans};

};

return get<2>(getSum(root));

}

};

花花酱 LeetCode 2251. Number of Flowers in Full Bloom

By zxi on April 27, 2022

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [start_i, end_i] means the i^th flower will be in full bloom from start_i to end_i (inclusive). You are also given a 0-indexed integer array persons of size n, where persons[i] is the time that the i^th person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the i^th person arrives.

Example 1:

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
Output: [1,2,2,2]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Example 2:

Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
Output: [2,2,1]
Explanation: The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

Constraints:

1 <= flowers.length <= 5 * 10⁴
flowers[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= persons.length <= 5 * 10⁴
1 <= persons[i] <= 10⁹

Solution: Prefix Sum + Binary Search

Use a treemap to store the counts (ordered by time t), when a flower begins to bloom at start, we increase m[start], when it dies at end, we decrease m[end+1]. prefix_sum[t] indicates the # of blooming flowers at time t.

For each people, use binary search to find the latest # of flowers before his arrival.

Time complexity: O(nlogn + mlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {

map<int, int> m{{0, 0}};

for (const auto& f : flowers)

++m[f[0]], --m[f[1] + 1];

int sum = 0;

for (auto& [t, c] : m)

c = sum += c;

vector<int> ans;

for (int t : persons)

ans.push_back(prev(m.upper_bound(t))->second);

return ans;

}

};