判断两棵树是否相同的代码能否编译运行？提交测试用例失败求分析

一、编译可行性 #

这段代码语法层面无错误，但要成功编译运行，需要满足两个前提：

1. 运行环境中已正确定义Node结构体/类，比如常见OJ环境的标准定义通常为：

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

2. 代码头部需包含必要头文件：#include <vector>（因为用到了std::vector容器）。

满足以上条件后，代码可以正常编译，且能通过部分测试用例（比如两棵完全相同的树、节点数量不同的树）。

二、提交失败的核心原因 #

你的逻辑存在根本性缺陷：仅通过中序遍历结果无法判定两棵树是否完全相同。中序遍历序列一致，不代表树的结构和节点位置完全匹配，典型反例如下：

• 树A：根节点为1，仅存在左子节点2
• 树B：根节点为1，仅存在右子节点2

两棵树的中序遍历结果均为[2, 1]，但结构完全不同，并非相同的树，但你的代码会错误返回true。

还有更复杂的反例：比如一棵三层满二叉树，和一棵左链式结构的树，可能中序遍历序列完全一致，但树的形态天差地别。

三、正确的实现思路 #

判断两棵树是否相同，必须同时满足三个条件：

• 当前节点的数值相等
• 左子树完全相同
• 右子树完全相同

基于递归的正确实现代码如下：

class Solution
{
public:
    bool isIdentical(Node *r1, Node *r2)
    {
        // 两个节点都为空，判定为相同
        if (r1 == nullptr && r2 == nullptr) {
            return true;
        }
        // 其中一个为空、另一个不为空，判定为不同
        if (r1 == nullptr || r2 == nullptr) {
            return false;
        }
        // 当前节点值相等，且左右子树都完全相同
        return (r1->data == r2->data) 
            && isIdentical(r1->left, r2->left) 
            && isIdentical(r1->right, r2->right);
    }
};

这种实现会逐节点对比结构与数值，能准确判定两棵树是否完全一致。

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