アルゴリズムに関する Skiena の本には、次の質問が含まれています。
1) n 個のノードが与えられた場合、O(n) 時間で二分木として与えられた式を評価します。
2) DAG で n ノードと m エッジが与えられた場合、O(n+m) 時間で DAG として与えられた式を評価します。
最初の質問の方法を考えることができました:
evaluate(node) {
if(node has children){
left_val = evaluate(node->left);
right_val = evaluate(node->right);
// find operation symbol for node and use it as
// val = left_val operation right_val
return val;
}
else {
return node_value;
}
}
各ノードに 1 回アクセスするため、O(n) 時間かかります。
この本には解決策がありませんので、これが正しいかどうか誰か教えてください。
また、誰でも2番目の質問の解決策を提案できますか?
ありがとう。