如何不考虑子节点顺序比较两棵通用树及XML DOM树是否相等

struct TreeNode{
    int data;
    vector<TreeNode*> subNodes;  // 指向当前节点所有子节点的指针列表
    TreeNode* parent;  // 指向当前节点的父节点
};

核心需求是忽略子节点顺序，只要节点数值、子树结构完全匹配就返回真，可根据场景选择以下两种实现方案：

基础逻辑边界判断 #

两种方案都需要先做前置校验：

• 若root1和root2均为nullptr，返回true
• 若root1和root2仅一个为nullptr，返回false
• 若两个节点的data值不相等，返回false
• 若两个节点的subNodes长度不一致，返回false

方案1：暴力匹配（适合子节点数量少的场景） #

通过标记已匹配子节点的方式完成无序校验，实现简单无额外哈希冲突风险：

bool compareDeep(TreeNode* root1, TreeNode* root2) {
    // 前置边界校验
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    if (root1->data != root2->data) return false;
    if (root1->subNodes.size() != root2->subNodes.size()) return false;
    
    int childCnt = root1->subNodes.size();
    vector<bool> used(childCnt, false); // 标记root2的子节点是否已被匹配
    
    // 逐个匹配root1的子节点
    for (int i = 0; i < childCnt; i++) {
        bool findMatch = false;
        for (int j = 0; j < childCnt; j++) {
            if (!used[j] && compareDeep(root1->subNodes[i], root2->subNodes[j])) {
                used[j] = true;
                findMatch = true;
                break;
            }
        }
        if (!findMatch) return false;
    }
    return true;
}

方案2：哈希优化（适合大节点数场景，如XML DOM比对） #

通过递归生成子树唯一哈希签名，排序后比对，性能远高于暴力匹配：

// 辅助函数：生成子树的唯一签名，自动消除子节点顺序影响
string getTreeHash(TreeNode* root) {
    if (!root) return "NULL"; // 空节点占位标识
    vector<string> childHashList;
    // 收集所有子节点的哈希
    for (auto child : root->subNodes) {
        childHashList.push_back(getTreeHash(child));
    }
    // 排序子节点哈希，消除顺序差异
    sort(childHashList.begin(), childHashList.end());
    // 拼接当前节点值和排序后的子节点哈希，生成当前节点唯一签名
    string curHash = to_string(root->data) + "[";
    for (auto& h : childHashList) {
        curHash += h + ",";
    }
    curHash += "]";
    return curHash;
}

bool compareDeep(TreeNode* root1, TreeNode* root2) {
    return getTreeHash(root1) == getTreeHash(root2);
}

如果担心字符串哈希碰撞，可以替换为双哈希规则（同时生成两种不同逻辑的哈希值比对），或用数值哈希进一步提升性能。
如果是XML DOM比对场景，只需把生成哈希时的to_string(root->data)替换为当前节点的标签名、排序后的属性键值对字符串，即可同时实现忽略元素顺序、忽略属性顺序的DOM比对需求。

内容的提问来源于stack exchange，提问作者Tejas Jadhav