回答編集履歴
2
説明を変更
answer
CHANGED
|
@@ -44,10 +44,12 @@
|
|
|
44
44
|
}
|
|
45
45
|
```
|
|
46
46
|
|
|
47
|
-
>
|
|
47
|
+
> 再帰を使ったDFSはスタックに書き換えることができるそうですが、再帰の戻り値を使ったDFSをスタックによるDFSへの書き換え方がわかりません。
|
|
48
48
|
|
|
49
|
-
|
|
49
|
+
「再帰関数は再帰呼び出しの代わりにスタックを用いて書き直すことができる」という話と、「DFSには再帰を使ったものとスタックを使ったものがある」という話がごっちゃになって、「再帰を使ったDFSを、スタックを使ったDFSに書き直すことができる」と勘違いしているように思えます。
|
|
50
50
|
|
|
51
|
+
再帰を使ったDFSをスタックを用いて書き直すことはできますが(上記ソース)、それは「スタックを使ったDFS」とは別物なので、単純にスタックをキューにするだけでBFSに変更することはできません。
|
|
52
|
+
|
|
51
53
|
そもそも、自身の値の計算に再帰の戻り値を使うということは、子要素の計算が終わらないと結果が確定しないということなので、子要素の計算を後回しにするBFSに変換するのは無理があります。
|
|
52
54
|
|
|
53
55
|
---
|
1
経路を全部保存する方法の提示
answer
CHANGED
|
@@ -48,4 +48,39 @@
|
|
|
48
48
|
|
|
49
49
|
こちらのコードのスタックをキューに変更してもまともに動作しないので、わざわざこんな書き方をするメリットはありません。
|
|
50
50
|
|
|
51
|
-
そもそも、自身の値の計算に再帰の戻り値を使うということは、子要素の計算が終わらないと結果が確定しないということなので、子要素の計算を後回しにするBFSに変換するのは無理があります。
|
|
51
|
+
そもそも、自身の値の計算に再帰の戻り値を使うということは、子要素の計算が終わらないと結果が確定しないということなので、子要素の計算を後回しにするBFSに変換するのは無理があります。
|
|
52
|
+
|
|
53
|
+
---
|
|
54
|
+
|
|
55
|
+
あと一応、DFSでたどった経路を全部保存して、後から逆順にたどるという手もあります。
|
|
56
|
+
こちらなら、スタックをキューにしても正しい回答が返ります。
|
|
57
|
+
ただ、これだとDFSではなく「DFSの逆順」にたどっていることになるのではないでしょうか。
|
|
58
|
+
```c++
|
|
59
|
+
int dfs(node* n){
|
|
60
|
+
vector<node*> v;
|
|
61
|
+
stack<node*> s;
|
|
62
|
+
s.push(n);
|
|
63
|
+
while (!s.empty()) {
|
|
64
|
+
n = s.top();
|
|
65
|
+
s.pop();
|
|
66
|
+
if (n == nullptr)
|
|
67
|
+
continue;
|
|
68
|
+
v.push_back(n);
|
|
69
|
+
s.push(n->left);
|
|
70
|
+
s.push(n->right);
|
|
71
|
+
}
|
|
72
|
+
|
|
73
|
+
int maximum = INT_MIN;
|
|
74
|
+
unordered_map<node*, int> m;
|
|
75
|
+
m[nullptr] = 0;
|
|
76
|
+
|
|
77
|
+
for (auto i = v.rbegin(); i != v.rend(); ++i) {
|
|
78
|
+
n = *i;
|
|
79
|
+
int left_value = m[n->left];
|
|
80
|
+
int right_value = m[n->right];
|
|
81
|
+
m[n] = n->value + max({ 0, left_value, right_value });
|
|
82
|
+
maximum = max({ maximum, m[n], left_value + right_value + n->value });
|
|
83
|
+
}
|
|
84
|
+
return maximum;
|
|
85
|
+
}
|
|
86
|
+
```
|