为何Leetcode第100题相同树中中序遍历解法失效？

你的直觉确实有误，单一的中序遍历（或仅用前序/后序单遍历）无法唯一确定一棵二叉树，这就是你测试用例失败的核心原因。

测试用例失败分析 #

你遇到的测试用例：

• p的树结构：根节点1，左子节点1，右子节点为空
• q的树结构：根节点1，左子节点为空，右子节点1

这两棵树的中序遍历结果都是[1,1]，所以你的代码会误判为相同，但它们的结构完全不同，因此预期输出为false。问题出在你的遍历逻辑没有记录空节点的信息，导致不同结构的树生成了相同的遍历序列。

你的代码存在的其他问题 #

除了遍历逻辑的缺陷，你的类成员变量plist和qlist会被LeetCode的批量测试复用，若不重置，前一次测试的结果会干扰后续测试，导致错误。

修正方案 #

方案1：改进遍历逻辑，记录空节点并重置容器

修改遍历方法，用特殊值（比如null）标记空节点，同时每次调用isSameTree时创建新的列表，避免跨测试用例污染：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        List<Integer> plist = new ArrayList<>();
        List<Integer> qlist = new ArrayList<>();
        inorder(p, plist);
        inorder(q, qlist);
        return plist.equals(qlist);
    }

    public void inorder(TreeNode root, List<Integer> lst) {
        if (root == null) {
            lst.add(null); // 标记空节点
            return;
        }
        inorder(root.left, lst);
        lst.add(root.val);
        inorder(root.right, lst);
    }
}

方案2：更高效的递归直接判断（推荐）

无需额外存储遍历序列，直接递归比较节点的存在性和值，同时验证左右子树结构：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两个节点都为空，结构一致
        if (p == null && q == null) return true;
        // 仅一个节点为空，结构不一致
        if (p == null || q == null) return false;
        // 当前节点值相同，递归比较左右子树
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

关键结论 #

如果想用遍历方式判断两棵树是否相同，必须同时记录节点值和空节点的位置，否则不同结构的树可能生成相同的遍历序列。另外，要注意避免测试用例之间的状态污染，不要使用类成员变量存储临时遍历结果。

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