评估表达式树

Question

Skiena关于算法的书包含以下问题:

1)给定n个节点,在O(n)时间内评估作为二叉树给出的表达式.

2)在给定n个节点和DAG中的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;
     }
}

由于我们访问每个节点一次,因此需要O(n)时间.

由于本书没有解决方案,任何人都可以告诉我这是否正确？

也可以有人建议第二个问题的解决方案.

谢谢.

Answer 1

第一种方式看起来很好.

对于DAG,如果您可以修改树以向每个节点添加缓存值,则可以使用具有小调整的相同算法,以便在操作员节点具有缓存值时不递归.这应该是O(n + m)时间(每个节点最多一次算术运算,每个边缘最多一次指针查找).明确:

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}