You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.
If node i has no left child then leftChild[i] will equal -1, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
Example 1:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true
Example 2:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false
Example 3:
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false
Constraints:
n == leftChild.length == rightChild.length1 <= n <= 104-1 <= leftChild[i], rightChild[i] <= n - 1
Companies: Facebook
Related Topics:
Tree, Depth-First Search, Breadth-First Search, Union Find, Graph, Binary Tree
Hints:
- Find the parent of each node.
- A valid tree must have nodes with only one parent and exactly one node with no parent.
- A node at most have a single parent
- There is exactly one node without parent -- the root node
- There is no cycle in the graph
- We can visit all the nodes from a random node.
// OJ: https://leetcode.com/problems/validate-binary-tree-nodes/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int> degree(n), parent(n, -1);
for (int i = 0; i < n; ++i) {
for (int ch : { leftChild[i], rightChild[i] }) {
if (ch == -1) continue;
if (parent[ch] != -1) return false; // A node at most have a single parent
++degree[ch];
++degree[i];
parent[ch] = i;
}
}
// Must have exactly one root
int root = -1;
for (int i = 0; i < n; ++i) {
if (parent[i] == -1) {
if (root != -1) return false;
root = i;
}
}
if (root == -1) return false;
// BFS Topological Sort to check cycle.
queue<int> q;
unordered_set<int> seen;
for (int i = 0; i < n; ++i) {
if (degree[i] <= 1) {
seen.insert(i);
q.push(i);
}
}
while (q.size()) {
int u = q.front(), p = parent[u];
q.pop();
if (p != -1 && seen.count(p) == 0 && --degree[p] <= 1) {
seen.insert(p);
q.push(p);
}
}
return seen.size() == n;
}
};// OJ: https://leetcode.com/problems/validate-binary-tree-nodes
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int> degree(n), parent(n, -1);
for (int i = 0; i < n; ++i) {
for (int ch : { leftChild[i], rightChild[i] }) {
if (ch == -1) continue;
if (parent[ch] != -1) return false; // A node at most have a single parent
++degree[ch];
++degree[i];
parent[ch] = i;
}
}
// Must have exactly one root
int root = -1;
for (int i = 0; i < n; ++i) {
if (parent[i] == -1) {
if (root != -1) return false;
root = i;
}
}
if (root == -1) return false;
// DFS to check cycle
unordered_set<int> seen;
function<bool(int)> dfs = [&](int u) {
if (u == -1) return true;
if (seen.count(u)) return false;
seen.insert(u);
return dfs(leftChild[u]) && dfs(rightChild[u]);
};
return dfs(root) && seen.size() == n;
}
};// OJ: https://leetcode.com/problems/validate-binary-tree-nodes
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
auto findRoot = [&]() {
unordered_set<int> s;
s.insert(leftChild.begin(), leftChild.end());
s.insert(rightChild.begin(), rightChild.end());
for (int i = 0; i < n; ++i) {
if (s.count(i) == 0) return i;
}
return -1;
};
int root = findRoot();
if (root == -1) return false;
unordered_set<int> seen;
function<bool(int)> dfs = [&](int u) {
if (u == -1) return true;
if (seen.count(u)) return false;
seen.insert(u);
return dfs(leftChild[u]) && dfs(rightChild[u]);
};
return dfs(root) && seen.size() == n;
}
};// OJ: https://leetcode.com/problems/validate-binary-tree-nodes
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
auto findRoot = [&]() {
unordered_set<int> s;
s.insert(leftChild.begin(), leftChild.end());
s.insert(rightChild.begin(), rightChild.end());
for (int i = 0; i < n; ++i) {
if (s.count(i) == 0) return i;
}
return -1;
};
int root = findRoot();
if (root == -1) return false;
unordered_set<int> seen{{root}};
queue<int> q{{root}};
while (q.size()) {
int u = q.front();
q.pop();
for (int ch : { leftChild[u], rightChild[u] }) {
if (ch == -1) continue;
if (seen.count(ch)) return false;
q.push(ch);
seen.insert(ch);
}
}
return seen.size() == n;
}
};// OJ: https://leetcode.com/problems/validate-binary-tree-nodes
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class UnionFind {
vector<int> id;
int cnt;
public:
UnionFind(int n) : id(n), cnt(n) {
iota(begin(id), end(id), 0);
}
int find(int a) { return id[a] == a ? a : (id[a] = find(id[a])); }
bool connect(int parent, int child) {
int pp = find(parent), cp = find(child);
if (pp == cp || cp != child) return false; // Return false if 1) parent and child are already connected, or 2) child already has a parent
id[cp] = pp;
--cnt;
return true;
}
int getCount() { return cnt; }
};
class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
UnionFind uf(n);
for (int p = 0; p < n; ++p) {
for (int ch : { leftChild[p], rightChild[p] }) {
if (ch == -1) continue;
if (!uf.connect(p, ch)) return false;
}
}
return uf.getCount() == 1;
}
};