ancestor Archives - Huahua's Tech Road

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;

}

};

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.

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]

Posts tagged as “ancestor”

花花酱 LeetCode 1766. Tree of Coprimes

Solution: DFS + Stack

C++

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

Solution: Brute Force

C++

Solution 2: Post order traversal

C++

Java

Python3