Posts tagged as “tree”

花花酱 LeetCode 1766. Tree of Coprimes

By zxi on February 20, 2021

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the i^th node’s value, and each edges[j] = [u_j, v_j] represents an edge between nodes u_j and v_j in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

Constraints:

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 10⁵
edges.length == n - 1
edges[j].length == 2
0 <= u_j, v_j < n
u_j != v_j

Solution: DFS + Stack

Pre-compute for coprimes for each number.

For each node, enumerate all it’s coprime numbers, find the deepest occurrence.

Time complexity: O(n * max(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {

constexpr int kMax = 50;

const int n = nums.size();

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<vector<int>> coprime(kMax + 1);

for (int i = 1; i <= kMax; ++i)

for (int j = 1; j <= kMax; ++j)

if (gcd(i, j) == 1) coprime[i].push_back(j);

vector<int> ans(n, INT_MAX);

vector<vector<pair<int, int>>> p(kMax + 1);

function<void(int, int)> dfs = [&](int cur, int d) {

int max_d = -1;

int ancestor = -1;

for (int co : coprime[nums[cur]])

if (!p[co].empty() && p[co].back().first > max_d) {

max_d = p[co].back().first;

ancestor = p[co].back().second;

}

ans[cur] = ancestor;

p[nums[cur]].emplace_back(d, cur);

for (int nxt : g[cur])

if (ans[nxt] == INT_MAX) dfs(nxt, d + 1);

p[nums[cur]].pop_back();

};

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1719. Number Of Ways To Reconstruct A Tree

By zxi on January 9, 2021

You are given an array pairs, where pairs[i] = [x_i, y_i], and:

There are no duplicates.
x_i < y_i

Let ways be the number of rooted trees that satisfy the following conditions:

The tree consists of nodes whose values appeared in pairs.
A pair [x_i, y_i] exists in pairs if and only if x_i is an ancestor of y_i or y_i is an ancestor of x_i.
Note: the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

0 if ways == 0
1 if ways == 1
2 if ways > 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

Constraints:

1 <= pairs.length <= 10⁵
1 <= x_i< y_i <= 500
The elements in pairs are unique.

Solution: Bitset

Time complexity: O(E*V)
Space complexity: O(V^2)

C++

// Author: Huahua

class Solution {

public:

int checkWays(vector<vector<int>>& pairs) {

// Construct a map, key is the node, value is the accessible nodes.

unordered_map<int, bitset<501>> m;

for (auto& e : pairs)

m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1;

// The tree must have one+ node/root that has paths to all the nodes.

if (!any_of(begin(m), end(m), [&m](const auto& kv) {

return kv.second.count() == m.size();})) return 0;

int multiple = 0;

for (const auto& e : pairs) {

// For each pair, check whether one can be the parent of another

// that can conver all the children nodes.

const auto& all = m[e[0]] | m[e[1]];

const int r0 = m[e[0]] == all;

const int r1 = m[e[1]] == all;

if (r0 + r1 == 0) return 0;

// If both can be parents, there can be multiple trees.

multiple |= r0 * r1;

}

return 1 + multiple;

}

};

Python3

# Author: Huahua

class Solution:

def checkWays(self, pairs: List[List[int]]) -> int:

m = defaultdict(set)

for u, v in pairs:

m[u] |= set((u, v))

m[v] |= set((u, v))

if not any(len(m[x]) == len(m) for x in m):

return 0

multiple = 0

for u, v in pairs:

union = m[u] | m[v]

ru, rv = int(m[u] == union), int(m[v] == union)

if not ru + rv: return 0

multiple |= ru * rv

return 1 + multiple

花花酱 LeetCode 1617. Count Subtrees With Max Distance Between Cities

By zxi on October 11, 2020

There are n cities numbered from 1 to n. You are given an array edges of size n-1, where edges[i] = [u_i, v_i] represents a bidirectional edge between cities u_i and v_i. There exists a unique path between each pair of cities. In other words, the cities form a tree.

A subtree is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.

For each d from 1 to n-1, find the number of subtrees in which the maximum distance between any two cities in the subtree is equal to d.

Return an array of size n-1 where the d^thelement (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to d.

Notice that the distance between the two cities is the number of edges in the path between them.

Example 1:

Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.

Example 2:

Input: n = 2, edges = [[1,2]]
Output: [1]

Example 3:

Input: n = 3, edges = [[1,2],[2,3]]
Output: [2,1]

Constraints:

2 <= n <= 15
edges.length == n-1
edges[i].length == 2
1 <= u_i, v_i <= n
All pairs (u_i, v_i) are distinct.

Solution1: Brute Force + Diameter of tree

Try all subtrees and find the diameter of that subtree (longest distance between any node)

Time complexity: O(2^n * n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges, int last = -1) {

vector<vector<int>> g(n);

for (const auto& e : edges)

g[e[0] - 1].push_back(e[1] - 1), g[e[1] - 1].push_back(e[0] - 1);

vector<int> seen(n, -1), seen2;

queue<int> q;

auto bfs = [&](int start, vector<int>& seen) -> pair<int, int> {

q.push(start);

seen[start] = 1;

int count = 0, dist = -1;

while (!q.empty()) {

int s = q.size();

while (s--) {

last = q.front(); q.pop();

++count;

for (int v : g[last])

if (seen[v] != -1 && !seen[v]++) q.push(v);

}

++dist;

}

return {dist, count};

};

vector<int> ans(n - 1);

for (int s = 0; s < 1 << n; ++s) {

if (__builtin_popcount(s) <= 1) continue;

fill(begin(seen), end(seen), -1);

for (int i = 0; i < n; ++i) if (s & (1 << i)) seen[i] = 0;

seen2 = seen;

const int start = 31 - __builtin_clz(s & (s - 1));

if (bfs(start, seen).second != __builtin_popcount(s)) continue;

++ans[bfs(last, seen2).first - 1];

}

return ans;

}

};

Solution 2: DP on Trees

dp[i][k][d] := # of subtrees rooted at i with tree diameter of d and the distance from i to the farthest node is k.

Time complexity: O(n^5)
Space complexity: O(n^3)

C++

// Author: Huahua, 4ms, 8.8MB

class Solution {

public:

vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0] - 1].push_back(e[1] - 1);

g[e[1] - 1].push_back(e[0] - 1);

}

vector<vector<vector<int>>> dp(n);

vector<int> sizes(n);

function<void(int, int)> dfs = [&](int u, int p) {

if (!dp[u].empty()) return;

dp[u] = vector<vector<int>>(n, vector<int>(n));

dp[u][0][0] = 1;

sizes[u] = 1;

for (int v : g[u]) {

if (v == p) continue;

dfs(v, u);

vector<vector<int>> dpu(dp[u]);

for (int d1 = 0; d1 < sizes[u]; ++d1)

for (int k1 = 0; k1 <= d1; ++k1) {

if (!dp[u][k1][d1]) continue;

for (int d2 = 0; d2 < sizes[v]; ++d2)

for (int k2 = 0; k2 <= d2; ++k2) {

const int d = max({d1, d2, k1 + k2 + 1});

const int k = max(k1, k2 + 1);

dpu[k][d] += dp[u][k1][d1] * dp[v][k2][d2];

}

swap(dpu, dp[u]);

sizes[u] += sizes[v];

}

};

vector<int> ans(n - 1);

dfs(0, -1);

for (int i = 0; i < n; ++i)

for (int k = 0; k < n; ++k)

for (int d = 1; d < n; ++d)

ans[d - 1] += dp[i][k][d];

return ans;

}

};

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

By zxi on July 25, 2020

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

Solution: Brute Force

Since n <= 1024, and distance <= 10, we can collect all leaf nodes and try all pairs.

Time complexity: O(|leaves|^2)
Space complexity: O(n)

C++

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

unordered_map<TreeNode*, TreeNode*> parents;

vector<TreeNode*> leaves;

function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) {

if (!c) return;

parents[c] = p;

dfs(c->left, c);

dfs(c->right, c);

if (!c->left && !c->right) leaves.push_back(c);

};

dfs(root, nullptr);

unordered_map<TreeNode*, int> a;

auto isGood = [&](TreeNode* n) -> int {

for (int i = 0; i < distance && n; ++i, n = parents[n])

if (a.count(n) && a[n] + i <= distance) return 1;

return 0;

};

int ans = 0;

for (int i = 0; i < leaves.size(); ++i) {

TreeNode* n1 = leaves[i];

a.clear();

for (int k = 0; k < distance && n1; ++k, n1 = parents[n1])

a[n1] = k;

for (int j = i + 1; j < leaves.size(); ++j)

ans += isGood(leaves[j]);

}

return ans;

}

};

Solution 2: Post order traversal

For each node, compute the # of good leaf pair under itself.
1. count the frequency of leaf node at distance 1, 2, …, d for both left and right child.
2. ans += l[i] * r[j] (i + j <= distance) cartesian product
3. increase the distance by 1 for each leaf node when pop
Time complexity: O(n*D^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

int ans = 0;

function<vector<int>(TreeNode*)> dfs

= [&](TreeNode* c) -> vector<int> {

// f[i] = number of leaves node at distance i.

vector<int> f(distance + 1);

if (!c) return f;

if (!c->left && !c->right) {

f[0] = 1; // a single leaf node

return f;

}

const vector<int>& l = dfs(c->left);

const vector<int>& r = dfs(c->right);

for (int i = 0; i + 1 <= distance; ++i)

for (int j = 0; i + j + 2 <= distance; ++j)

ans += l[i] * r[j];

for (int i = 0; i < distance; ++i)

f[i + 1] = l[i] + r[i];

return f;

};

dfs(root);

return ans;

}

};

Java

class Solution {

private int D;

private int ans;

public int countPairs(TreeNode root, int distance) {

this.D = distance;

this.ans = 0;

dfs(root);

return ans;

}

private int[] dfs(TreeNode root) {

int[] f = new int[D + 1];

if (root == null) return f;

if (root.left == null && root.right == null) {

f[0] = 1;

return f;

}

int[] fl = dfs(root.left);

int[] fr = dfs(root.right);

for (int i = 0; i + 1 <= D; ++i)

for (int j = 0; i + j + 2 <= D; ++j)

this.ans += fl[i] * fr[j];

for (int i = 0; i < D; ++i)

f[i + 1] = fl[i] + fr[i];

return f;

}

Python3

# Author: Huahua

class Solution:

def countPairs(self, root: TreeNode, D: int) -> int:

def dfs(node):

f = [0] * (D + 1)

if not node: return f, 0

if not node.left and not node.right:

f[0] = 1

return f, 0

fl, pl = dfs(node.left)

fr, pr = dfs(node.right)

pairs = 0

for dl, cl in enumerate(fl):

for dr, cr in enumerate(fr):

if dl + dr + 2 <= D: pairs += cl * cr

for i in range(D):

f[i + 1] = fl[i] + fr[i]

return f, pl + pr + pairs

return dfs(root)[1]

花花酱 LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label

By zxi on July 18, 2020

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [a_i, b_i], which means there is an edge between nodes a_i and b_i in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the i^th node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

Example 4:

1 2	<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa" <strong>Output:</strong> [1,2,1,1,2,1]

Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]

Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
labels.length == n
labels is consisting of only of lower-case English letters.

Solution: Post order traversal + hashtable

For each label, record the count. When visiting a node, we first record the current count of its label as before, and traverse its children, when done, increment the current count, ans[i] = current – before.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> countSubTrees(int n, vector<vector<int>>& edges,

string_view labels) {

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<int> seen(n);

vector<int> count(26);

vector<int> ans(n);

function<void(int)> postOrder = [&](int i) {

if (seen[i]++) return;

int before = count[labels[i] - 'a'];

for (int j : g[i]) postOrder(j);

ans[i] = ++count[labels[i] - 'a'] - before;

};

postOrder(0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private List<List<Integer>> g;

private String labels;

private int[] ans;

private int[] seen;

private int[] count;

public int[] countSubTrees(int n, int[][] edges, String labels) {

this.g = new ArrayList<List<Integer>>(n);

this.labels = labels;

for (int i = 0; i < n; ++i)

this.g.add(new ArrayList<Integer>());

for (int[] e : edges) {

this.g.get(e[0]).add(e[1]);

this.g.get(e[1]).add(e[0]);

}

this.ans = new int[n];

this.seen = new int[n];

this.count = new int[26];

this.postOrder(0);

return ans;

}

private void postOrder(int i) {

if (this.seen[i]++ > 0) return;

int before = this.count[this.labels.charAt(i) - 'a'];

for (int j : this.g.get(i)) this.postOrder(j);

this.ans[i] = ++this.count[this.labels.charAt(i) - 'a'] - before;

}

Python3

# Author: Huahua

class Solution:

def countSubTrees(self, n: int, edges: List[List[int]],

labels: str) -> List[int]:

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

g[v].append(u)

seen = [False] * n

count = [0] * 26

ans = [0] * n

def postOrder(i):

if seen[i]: return

seen[i] = True

before = count[ord(labels[i]) - ord('a')]

for j in g[i]: postOrder(j)

count[ord(labels[i]) - ord('a')] += 1

ans[i] = count[ord(labels[i]) - ord('a')] - before

postOrder(0)

return ans