推 good5dog5: else if (root->value==-1)才是代表有visit過吧？ 01/06 12:14
純分享1.2
bool IsCycleExist(Node *root)
{
Node* l,r;
l = root->left;
r = root->right;
if(root == Null)
return False;
else if(root->value != -1)
return True;
else{
root->value = -1;
return (IsCycleExist(root->left)||IsCycleExist(root->right));
}
想法是讓他左右子樹一直遞迴下去，每遞迴一次就把值設成-1
一檢查到有value為-1的node 就return false
再將左右子樹的結果OR起來 就會是答案
是用BFS概念寫的
不過跑完之後值就會都變成-1
這是在不改變他資料結構的前提下 我盡力想出來的方法@@"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.185.168
※ 編輯: w29697146 來自: 114.32.185.168 (01/15 21:40)
※ 編輯: w29697146 來自: 114.32.185.168 (01/15 21:41)
※ 編輯: w29697146 來自: 114.32.185.113 (01/30 22:10)