Easy

题目描述

给你两棵二叉树的根节点 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] 内
  • -10^4 <= Node.val <= 10^4

解题思路

这道题要求判断两棵二叉树是否完全相同，包括结构和节点值都要相同。

解法分析：

  1. 递归解法（推荐）：这是最直观的解法。对于每个节点，我们需要检查：

    • 如果两个节点都为空，则相同
    • 如果只有一个节点为空，则不同
    • 如果两个节点都不为空，需要检查值是否相等，并递归检查左右子树

  2. 迭代解法：使用栈或队列进行层序遍历，同时遍历两棵树并比较对应位置的节点。

递归解法思路：

  • 基准情况：如果 p 和 q 都为 null，返回 true
  • 如果 p 和 q 中只有一个为 null，返回 false
  • 如果 p 和 q 的值不相等，返回 false
  • 递归检查左子树和右子树是否都相同

这种方法时间复杂度为 O(min(m,n))，其中 m 和 n 分别是两棵树的节点数，空间复杂度为 O(min(m,n))（递归栈的深度）。

代码实现

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两个节点都为空，则相同
        if (p == nullptr && q == nullptr) {
            return true;
        }
        
        // 如果只有一个节点为空，则不同
        if (p == nullptr || q == nullptr) {
            return false;
        }
        
        // 如果节点值不相等，则不同
        if (p->val != q->val) {
            return false;
        }
        
        // 递归检查左右子树
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # 如果两个节点都为空，则相同
        if not p and not q:
            return True
        
        # 如果只有一个节点为空，则不同
        if not p or not q:
            return False
        
        # 如果节点值不相等，则不同
        if p.val != q.val:
            return False
        
        # 递归检查左右子树
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

public class Solution {
    public bool IsSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都为空，则相同
        if (p == null && q == null) {
            return true;
        }
        
        // 如果只有一个节点为空，则不同
        if (p == null || q == null) {
            return false;
        }
        
        // 如果节点值不相等，则不同
        if (p.val != q.val) {
            return false;
        }
        
        // 递归检查左右子树
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}

var isSameTree = function(p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val !== q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(min(m,n))其中 m 和 n 分别是两棵树的节点数，最坏情况需要遍历所有节点
空间复杂度O(min(m,n))递归调用栈的深度，等于树的高度，最坏情况为节点数