# 说道FB和谷歌出现的怪题 - 判断是否可以形成 Binary Tree

input是 array of tree node，问这些nodes 是否可以形成一个binary tree， return true or false。

``````class TreeNode {
TreeNode left;
TreeNode right;
int val;
}
``````

`````` private boolean isOneTree(List<TreeNode> nodes){
Set<TreeNode> roots = new HashSet<>(nodes);
Set<TreeNode> whole = new HashSet<>(nodes);
Set<TreeNode> checked = new HashSet<>();
for (TreeNode node : nodes){

if (!roots.contains(node))continue;
Set<TreeNode> visited = new HashSet<>();
// have cycle or outlier node
if (!dfs(node, roots, visited, true, whole, checked)){
return false;
}
}
return roots.size() == 1;
}
private boolean dfs(TreeNode root, Set<TreeNode> set, Set<TreeNode> visited,
boolean isOrig, Set<TreeNode> whole, Set<TreeNode> checked){
if (root == null)return true;
// there is a cycle in tree
if (visited.contains(root))return false;
if (!whole.contains(root))return false;
if (checked.contains(root)){
set.remove(root);
return true;
} // avoid multiple times access checked subtree node.

// make sure only remove subtree node.
if (!isOrig){
set.remove(root);
}
return dfs(root.left, set, visited, false，whole, checked) && dfs(root.right, set, visited, false,whole,checked);
}
``````

``````	public boolean isBinaryTree(TreeNode[] nodes) {
Set<TreeNode> s = new HashSet<>();
for (TreeNode node : nodes) {
}

for (TreeNode node : nodes) {
if (node.left != null) {
if (!s.contains(node.left)) {
return false;
}
s.remove(node.left);
}
if (node.right != null) {
if (!s.contains(node.right)) {
return false;
}
s.remove(node.right);
}
}

return s.size() == 1;
}
``````
1 Like

``````
public boolean isBinaryTree(List<TreeNode> nodes)
{
Set<TreeNode> set = HashSet<>();
for(TreeNode node : nodes) set.add(node);
for(TreeNode root : nodes)
{
if(!set.contains(root)) continue;
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> seen = HashSet<>();
while(queue.size() != null)
{
TreeNode node = queue.poll();
if(node != null)
{
// not exist
if(!set.contains(node))
return false;
// cycle?
if(seen.contains(node))
return false;
}
}
for(TreeNode node : seen)
if(node != root)
set.remove(node);
}
// Only root left?
return set.size() == 1;
}
``````

``````     A            B                    C
/                 \
B                     A``````

``````	public boolean isBinaryTree(TreeNode[] nodes) {
Set<TreeNode> s = new HashSet<>();
for (TreeNode node : nodes) {
}

int edges = 0;
for (TreeNode node : nodes) {
if (node.left != null) {
edges++;
if (!s.contains(node.left)) {
return false;
}
s.remove(node.left);
}
if (node.right != null) {
edges++;
if (!s.contains(node.right)) {
return false;
}
s.remove(node.right);
}
}

if (edges != s.size() - 1) {
return false;
}
return s.size() == 1;
}
``````

edges = 2
n = 3

``````	public boolean isBinaryTree(TreeNode[] nodes) {
Set<TreeNode> s = new HashSet<>();
for (TreeNode node : nodes) {
}

for (TreeNode node : nodes) {
if (node.left != null) {
if (!s.contains(node.left)) {
return false;
}
s.remove(node.left);
}
if (node.right != null) {
if (!s.contains(node.right)) {
return false;
}
s.remove(node.right);
}
}

if (s.size() != 1) {
return false;
}
return traverse(s.iterator().next(), s.size());
}

private boolean traverse(TreeNode root, int n) {
Queue<TreeNode> q = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
while (!q.isEmpty()) {
TreeNode cur = q.poll();
n--;
if (cur.left != null) {
if (visited.contains(cur.left)) {
return false;
}
}
if (cur.right != null) {
if (visited.contains(cur.right)) {
return false;
}
}
}

return n == 0;
}
``````

1 Like

``````    public boolean isBinaryTree(List<TreeNode> nodes)
{
Set<TreeNode> set = HashSet<>();
Set<TreeNode> visited = HashSet<>();
for(TreeNode node : nodes) set.add(node);
for(TreeNode root : nodes)
{
if(!set.contains(root)) continue;
Queue<TreeNode> queue = new LinkedList<>();
Set<TreeNode> seen = HashSet<>();
while(queue.size() != 0)
{
TreeNode node = queue.poll();
if(node != null)
{
// cycle? dup?
if(seen.contains(node))
return false;
// not exist
if(!set.contains(node))
return false;
if(visited(node))
continue;
}
}
for(TreeNode node : seen)  if(node != root) set.remove(node);
}
// Only root left?
return set.size() == 1;
}
``````

1 Like

1 Like