如何判断两棵二叉树包含相同节点（不可展平为数组）

你当前实现的isIdentical判定逻辑是两棵树结构完全同构、对应位置值完全相等才返回1：代码里强制要求root1的左子树必须和root2的左子树逐位匹配、root1的右子树必须和root2的右子树逐位匹配，完全没有考虑「节点排列顺序不影响、元素集合一致就算相等」的规则。
你测试用例中树A的4、5分别为根的左右孩子，树B的5、4分别为根的左右孩子，代码递归到子树层时会直接判定左右子树不匹配返回0，和预期结果不符。

题目明确禁止将树展平为数组，因此不需要提前把节点导出到线性结构存储，可以直接利用二叉搜索树的原生查找特性完成校验，逻辑如下：

• 空状态前置校验：两棵树同时为空直接判定相等，仅一棵为空直接判定不相等
• 节点数校验：两棵树节点总数不一致时，元素集合必然不同，直接返回不相等
• 全节点存在校验：遍历其中一棵树的所有节点，每访问一个节点就去另一棵BST中执行标准值查找，只要有一个值查找失败就判定不相等
• 所有节点校验通过则判定两棵树相等

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// BST标准查找：判断树中是否存在目标值
int bstContains(struct Node* root, int target) {
    if (root == NULL) return 0;
    if (root->data == target) return 1;
    return target < root->data ? bstContains(root->left, target) : bstContains(root->right, target);
}

// 递归统计树的节点总数
int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 递归遍历root1所有节点，校验每个值都在root2中存在
int checkAllMatch(struct Node* root1, struct Node* root2) {
    if (root1 == NULL) return 1;
    return bstContains(root2, root1->data) 
        && checkAllMatch(root1->left, root2) 
        && checkAllMatch(root1->right, root2);
}

int isIdentical(struct Node* root1, struct Node* root2)
{
    if (root1 == NULL && root2 == NULL)
        return 1;
    if (root1 == NULL || root2 == NULL)
        return 0;
    if (countNodes(root1) != countNodes(root2))
        return 0;
    return checkAllMatch(root1, root2);
}

• 全程没有将树结构展平为数组，所有操作直接在原树结构上递归完成，符合题目限制
• 不要求两棵树的节点排列、子树结构一致，只要包含的节点值完全相同就会返回1，你提到的4、5节点位置互换的测试用例会正确返回1
• 平衡BST场景下时间复杂度为O(nlogn)，最坏斜树场景下时间复杂度为O(n²)，没有额外的线性存储开销

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