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

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

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

这里要注意TreeNode 的 child node 有可能不在 input 的 nodes 里,这时候就是false。
思路可以考虑先把所有的node 放到一个set。然后遍历 input array, 把 child node 从set 里全部删掉,如果child node 不在set 里,直接返回 false。
最后 set 应该只剩下一个parent。set的size 不对就返回 false。

欢迎读后写一下代码试试,回帖发一下代码。

 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;
            }
            checked.add(node);
        }
        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);
    }

没有写test case 所以不保证对。还请大家指点

为什么需要两个set,应该一个就够了啊。
感觉写的复杂了。只要用一个set应该就够了。

写了一下,大概这个意思

	public boolean isBinaryTree(TreeNode[] nodes) {
		Set<TreeNode> s = new HashSet<>();
		for (TreeNode node : nodes) {
			s.add(node);
		}
		
		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<>();
    		queue.add(root);
    		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;
    				seen.add(node);
    				queue.add(node.left);
    				queue.add(node.right);				
    			}
    		}
		for(TreeNode node : seen)
			if(node != root)
				set.remove(node);
    	}
    	// Only root left?
    	return set.size() == 1;
    }

这个queue 有意义吗?

嗯,做了个BFS,感觉如果只remove child出现这种case会不会不好使:

     A            B                    C
   /                 \
B                     A

这是个两个node形成的环吗?

看下我上面的解法吧 :innocent:

是三个node,node A和node B互相指着,node c底下啥都没有。

如果光check一层的话,node A和B能互相delete掉,c还在。

image

好bug!
我可以加个check,假设有n个node,edges.length != n - 1 就要false

更新了代码

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

		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
好像这样也不行

在原来的逻辑基础上加了个level order traversal

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

		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<>();
		q.add(root);
		Set<TreeNode> visited = new HashSet<>();
		while (!q.isEmpty()) {
			TreeNode cur = q.poll();
			n--;
			visited.add(cur);
			if (cur.left != null) {
				if (visited.contains(cur.left)) {
					return false;
				}
				q.add(cur.left);
			}
			if (cur.right != null) {
				if (visited.contains(cur.right)) {
					return false;
				}
				q.add(cur.right);
			}
		}
		
		return n == 0;
	}

这里的 visited 其实没必要

1 Like

我感觉不加一个visited我那个也是错的。。。:scream:

    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<>();
    		queue.add(root);
    		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;					
    				seen.add(node);		
    				if(visited(node))
    					continue;    		
    				queue.add(node.left);
    				queue.add(node.right);				
    			}
    		}
    		for(TreeNode node : seen)  if(node != root) set.remove(node);
    		visited.add(node);
    	}
    	// Only root left?
    	return set.size() == 1;
    }

啥意思?

哈哈哈,我脑子抽了,改下改下

还是不太理解代码的逻辑,你没找到root就用level order 吗?

老师我是先看见sub tree就把里面的所有除了起始node都从set里面删掉并且把主node放到visited里面。下次我bfs的时候碰到visited过的起始node直接删,不traverse sub tree了。。。

感觉现在在写bug。。。我还是学习下你的吧:joy:

1 Like

这部分有bug。应该是return traverse(s.iterator().next(), nodes.size());这样确保每个node都遍历到。这个s是set已经知道大小是1了,只是为了找到root

1 Like