如何将递归实现的树同构判断函数转为迭代算法？

迭代实现思路 #

递归版本的核心逻辑是验证两种匹配分支的“或”关系：要么两棵树的对应子树直接匹配，要么交叉匹配（左对右、右对左）。迭代实现用栈模拟递归调用栈，通过栈帧标记当前是否已尝试过第一种分支，以此模拟递归的短路判断逻辑。

迭代代码实现 #

#include <stack>
using namespace std;

struct node {
    node* left;
    node* right;
};

// 栈帧结构体：存储待检查的节点对，以及是否已尝试过第一种匹配分支
struct StackFrame {
    node* a;
    node* b;
    bool triedFirst;
    StackFrame(node* a_, node* b_, bool tf_) : a(a_), b(b_), triedFirst(tf_) {}
};

bool isIsomorphic(node* n1, node* n2) {
    stack<StackFrame> stk;
    stk.emplace(n1, n2, false);

    while (!stk.empty()) {
        StackFrame frame = stk.top();
        stk.pop();

        node* a = frame.a;
        node* b = frame.b;

        // 终止条件处理
        if (a == nullptr && b == nullptr) {
            continue;
        }
        if (a == nullptr || b == nullptr) {
            return false;
        }

        if (!frame.triedFirst) {
            // 先尝试第一种分支：左子树对左子树，右子树对右子树
            stk.emplace(a, b, true);
            // 栈后进先出，先压右节点对，再压左节点对，保证先处理左子树匹配
            stk.emplace(a->right, b->right, false);
            stk.emplace(a->left, b->left, false);
        } else {
            // 第一种分支失败，尝试第二种分支：左子树对右子树，右子树对左子树
            stk.emplace(a->right, b->left, false);
            stk.emplace(a->left, b->right, false);
        }
    }

    // 所有匹配检查通过
    return true;
}

代码逻辑说明 #

1. 栈帧设计：每个栈帧包含待检查的两个节点，以及triedFirst标记，用于区分是否已尝试过第一种匹配分支。
2. 终止条件：弹出栈帧后先检查节点是否为空，两个都空则继续处理其他帧；一个空一个非空直接返回false。
3. 分支处理：
   • 首次处理节点对时，先将当前帧标记为已尝试第一种分支后重新压栈，再压入第一种分支的左右子节点对，保证先按递归顺序处理左对左、右对右的匹配。
   • 若第一种分支处理失败（后续帧触发返回false后回溯），则处理第二种分支的交叉匹配。
4. 短路特性：只要任意分支的所有子节点对都匹配，栈会被清空并返回true；若任意节点对不匹配，立即返回false，终止后续检查。

内容的提问来源于stack exchange，提问作者James Deen