a*********0
发帖数: 2727 | 1 给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个数
组中的节点所构成的树是tree
我的想法是用个map记录，-1表示没在数组中出现过。出现了就转为1。大致code
有没有更好的方法?
bool isTree(vector& a)
{
size_t n=a.size();
unordered_map nodeMap;
for(size_t i=0;i
if(nodeMap[a[i]]==-1) {
nodeMap[a[i]]=1;
} else {
nodeMap[a[i]]=0;
}
if(nodeMap[a[i]->next]==0) {
nodeMap[a[i]->next]=1;
}
}
ListNode* root=NULL;
for(auto itr=nodeMap.begin(); itr!=nodeMap.end(); itr++) {
if(itr->second==0) {
root=itr->first;
} else if(itr->second<0){
return false;
}
}
return dfs(root);
}
// use dfs to decide if it's a tree
bool dfs(root){
} |
n******n
发帖数: 12088 | 2 判断构成的树是tree？
【在 a*********0 的大作中提到】
: 给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个数
: 组中的节点所构成的树是tree
: 我的想法是用个map记录，-1表示没在数组中出现过。出现了就转为1。大致code
: 有没有更好的方法?
: bool isTree(vector& a)
: {
: size_t n=a.size();
: unordered_map nodeMap;
: for(size_t i=0;i: if(nodeMap[a[i]]==-1) {
|
a*********0
发帖数: 2727 | 3 如果指向数组外点就return false
【在 n******n 的大作中提到】
: 判断构成的树是tree？
|
P******r
发帖数: 1342 | |
x*****n
发帖数: 195 | |
a*********0
发帖数: 2727 | 6 不一定， 比如这样的A->B
(B->C)
->C
【在 x*****n 的大作中提到】
: 不构成环且不构成森林吧，用bfs就可以了。
|
x*****n
发帖数: 195 | 7 没问题啊，这个不构成树。典型的生成树算法dfs和bfs都可以做的。
【在 a*********0 的大作中提到】
: 不一定， 比如这样的A->B
: (B->C)
: ->C
|
