69.相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

• 输入：p = [1,2,3], q = [1,2,3]
• 输出：true

示例 2：

• 输入：p = [1,2], q = [1,null,2]
• 输出：false

示例 3：

• 输入：p = [1,2,1], q = [1,1,2]
• 输出：false

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

思路

同步的齐步走比较两棵树

想判断两棵树是否相同，我们让两个指针p和q同时从格子的根节点出发，步调一致的往下走，走到哪里就比较哪里:

两棵树相同 = 根节点相同 且 左子树相同 且 右子树相同

左子树相同和右子树相同这两个子问题，和整棵树是否相同都是同一个问题，规模变小了。

这正是递归的标志。

递归的两个要素

1. 递归终止条件：当我们同时走到p和q的某个位置时，先看他们是不是空 - 两个都为空(p == null && q == null): 说明两棵子树都到底了，且一路都匹配，返回true - 只有一个为空(一个null一个不为null): 说明结构不一样(一边有节点，一边没有)，返回false - 两个都不为空，那就比较它们的值了，进入下一步

2. 递推关系(两个都非空时)

• 先比较当前两个节点的值: 如果p.val != q.val，直接返回false
• 值相同的话，再递归比较，左子树 vs 右子树，两个都为true才算相同

用一句话概括:

当前值相等 且 递归(p.left, q.left) 且递归(p.right, q.right)

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        // 1. base case 之一：两个都为空 → 走到底且一路匹配，相同
        if (p == null && q == null) {
            return true
        }

        // 2. base case 之二：只有一个为空 → 结构不同，不相同
        if (p == null || q == null) {
            return false
        }

        // 3. 走到这里说明两个都非空：先比较当前值
        if (p.`val` != q.`val`) {
            return false
        }

        // 4. 递推关系：值相等，再递归比较左子树 且 右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
}

复杂度

• 时间复杂度: O(n)：n 是两棵树中较小的节点数（一旦某处不匹配就短路返回）。最坏情况（两树完全相同）下，每个节点都要访问一次，为 O(n)。
• 空间复杂度: O(h)：h 是树的高度，来自递归调用栈的深度。最坏情况（树退化成链）为 O(n)，平衡树为 O(log n)。

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!