从递归到迭代函数（树同构）

Question

我想将一个使用递归的函数转换为迭代算法。

我已经查看了几个关于如何从递归切换到迭代的解释，但大多数都局限于简单的情况，比如阶乘，其中递归函数只调用自身一次。

在我的情况下，我正在处理一个检查两棵树是否同构的函数：

- 如果一棵树可以通过执行任意数量的翻转（即交换节点的左子树和右子树）来得到另一棵树，则这两棵树是同构的，而且无论节点的值是否不同，都可以进行任意数量的翻转。

同构树的一个例子：

这是递归版本，其中递归调用的次数呈指数增长。

bool isIsomorphic(node* n1, node *n2){
 if (n1 == NULL && n2 == NULL)
    return true;
 if (n1 == NULL || n2 == NULL)
    return false;
 return
 (isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))||
 (isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left));
}

如何将这个问题写成迭代算法？

- James Deen

Answer 1

当我们看递归调用的表达式时，我们可以看到在递归调用被启动时有不同的“状态”。

   (isIsomorphic(n1->left,n2->left) && isIsomorphic(n1->right,n2->right))||
//  ^ initial state                    ^ had success on left/left       ^ success
   (isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left));
//  ^ failure on one of above           ^ had success on left/right     ^ success

如果我们使用整数来列举状态，我们只需要4个中间状态（不包括成功/失败）。我们可以将转换形象地描述如下：

                         state 0
                            |
                       (left, left)
                      /            \
                     |           state 3
                      \             |
                       \      (right, right)
                        \    /              \
                         \  /             success
                          \/
                       state 1
                          |
                     (left, right)                  
                    /             \
                failure         state 2
                                   |
                             (right, left)
                            /             \
                        failure         success

这些对子表示递归调用中组合的子节点。左侧分支表示所分析的子树不同构，而右侧分支表示它们是同构的。

在基于堆栈的解决方案中，你可以将状态添加到堆栈项中，这样当你回溯时，无论成功还是失败，都可以知道应该得到什么结果状态：

状态	推动	弹出原因	下一个状态
0	左, 左	同构	3
0	左, 左	非同构	1
1	左, 右	同构	2
1	左, 右	非同构	非同构
2	右, 左	同构	同构
2	右, 左	非同构	非同构
3	右, 右	同构	同构
3	右, 右	非同构	1

这是我们需要的堆栈实现（使用C语言）：

// -------- Stack implemented as a linked list -------
struct stack_item {
    struct node* n1; 
    struct node* n2;
    int state;
    struct stack_item* next;
};

struct stack_item* create_item(struct node* n1, struct node* n2, int state) {
    struct stack_item* newitem = malloc(sizeof *newitem);
    newitem->n1 = n1;
    newitem->n2 = n2;
    newitem->state = state;
    newitem->next = NULL;
    return newitem;
}

void stack_push(struct stack_item** stack, struct stack_item* item) {
    item->next = *stack;
    *stack = item;
}

struct stack_item* stack_pop(struct stack_item** stack) {
    struct stack_item* popitem = *stack;
    *stack = (*stack)->next;
    return popitem;
}

这是isomophic函数本身的代码：

int isomorphic(struct node* n1, struct node* n2) {
    struct stack_item* stack = NULL;
    struct stack_item* item = create_item(n1, n2, 0);
    
    while (1) {
        if (!item->n1 && !item->n2) {
            // success
            do {
                free(item);
                if (!stack) return 1; // overall success
                item = stack_pop(&stack);
            } while (item->state >= 2);
            item->state ^= 3;
        } else if (!item->n1 || !item->n2) {
            // failure
            do {
                free(item);
                if (!stack) return 0; // overall failure
                item = stack_pop(&stack);
            } while (item->state == 1 || item->state == 2); // failure
            item->state = 1;
        }
        stack_push(&stack, item);
        // The pair to look into depends on the state:
        item = create_item(
            (item->state & 2) ? item->n1->right : item->n1->left, 
            (item->state & 1) ? item->n2->right : item->n2->left, 
            0
        );
    }
}

备注

原始的递归算法并不是最优的，因为如果第一个递归调用返回true，而第二个调用没有返回true，那么第二行的两个备选递归调用都不可能同时返回true。所以实际上，递归版本可以改进为：

   isIsomorphic(n1->left,n2->left) 
        ? isIsomorphic(n1->right,n2->right)
        : isIsomorphic(n1->left,n2->right) && isIsomorphic(n1->right,n2->left);

这意味着再也没有需要在同一执行上下文中进行四次递归调用的情况了。

迭代函数需要相应地进行调整，以便当失败返回到状态-3节点时，该节点也会失败（循环必须继续）。

        // failure
        do {
            free(item);
            if (!stack) return 0; // overall failure
            item = stack_pop(&stack);
        } while (item->state >= 1); // failure (also for state 3)

- trincot