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;
}
这样呢？
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形成的环吗？
看下我上面的解法吧 
是三个node，node A和node B互相指着，node c底下啥都没有。
如果光check一层的话，node A和B能互相delete掉，c还在。
好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 其实没必要
我感觉不加一个visited我那个也是错的。。。
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。。。我还是学习下你的吧
这部分有bug。应该是return traverse(s.iterator().next(), nodes.size());这样确保每个node都遍历到。这个s是set已经知道大小是1了，只是为了找到root