LeetCode 100题：TreeNode工作原理及Same Tree测试问题咨询

我之前在Stack Overflow上得到过帮助，现在来这里提问。这个问题和LeetCode第100题有关，我完全搞不懂TreeNode到底是怎么工作的。

TreeNode的类定义如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

这道题的第一个测试用例给出两棵树的输入是：

q = [1,2,3]
p = [1,2,3]

题目要求两棵树相同时返回True，否则返回False。我原本写了这段代码，以为能通过测试：

return q.val == p.val and q.left == p.left and q.right == p.right

但实际返回的是False，不是预期的True。我还试过只返回q.val，预期输出是1，结果却得到了True。

我完全摸不着头脑，之前在Jupyter Notebook里自己定义TreeNode类，然后这么创建两棵树：

q = TreeNode()
q.val = 1
q.left = 2
q.right = 3

对p做同样操作后，运行这段判断代码：

q.val == p.val and q.left == p.left and q.right == p.right

结果得到了True。我到底哪里理解错了？忽略了什么？

问题根源：你搞混了LeetCode的输入结构和自己错误的树构造方式 #

1. LeetCode的测试用例不是直接给数组，而是已经转成TreeNode结构

题目里写的[1,2,3]是LeetCode用来表示树的序列化写法，后台会自动把它转换成真正的TreeNode对象结构：

• 根节点是TreeNode(val=1)
• 根节点的left是TreeNode(val=2)（它的left和right都是None）
• 根节点的right是TreeNode(val=3)（它的left和right都是None）

你在LeetCode里拿到的p和q已经是这种递归的TreeNode实例，不是数组。

2. 你的错误代码做了「引用比较」，而非「结构比较」

你写的q.left == p.left是在比较两个TreeNode对象的内存地址是否相同，而不是比较它们的结构是否一致。哪怕两个节点的val、left、right完全一样，只要是不同的实例，这个比较就会返回False。

3. 你在Jupyter里的树构造是错误的

你把q.left直接赋值成了整数2，而不是TreeNode(2)。这时候q.left是普通整数，和p的left（也是整数2）比较当然相等，但这根本不是符合题目要求的树结构——TreeNode的left和right必须是TreeNode实例或者None，不能是数值。

正确的判断逻辑 #

要判断两棵树是否相同，必须递归地比较每个节点的val，以及它们的左、右子树是否相同：

def isSameTree(p: TreeNode, q: TreeNode) -> bool:
    # 两个节点都为空，说明相同
    if not p and not q:
        return True
    # 一个空一个非空，直接不同
    if not p or not q:
        return False
    # 当前节点值相同，再递归比较左右子树
    return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

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