08、相同的树

厨子大约 3 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招

哈喽，大家好，我是厨子，今天给大家写一下相同的树

https://leetcode.cn/problems/same-tree/?envType=problem-list-v2&envId=binary-treeopen in new window

题目描述

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

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

示例 1:

输入：p = [1,2,3], q = [1,2,3]
输出：true
    p:      q:
    1       1
   / \     / \
  2   3   2   3

示例 2:

输入：p = [1,2], q = [1,null,2]
输出：false
    p:      q:
    1       1
   /         \
  2           2

示例 3:

输入：p = [1,2,1], q = [1,1,2]
输出：false
    p:      q:
    1       1
   / \     / \
  2   1   1   2

约束条件:

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

解题思路

这道题是经典的递归问题，需要同时遍历两棵树，比较对应位置的节点。

核心思想

两棵树相同的条件：

当前节点的值相同
左子树相同
右子树相同

图解示例

示例1：相同的树

步骤1: 比较根节点
p:  1        q:  1
   / \          / \
  2   3        2   3
值相同 ✓

步骤2: 递归比较左子树
p:  2        q:  2
值相同 ✓，且都是叶子节点

步骤3: 递归比较右子树
p:  3        q:  3
值相同 ✓，且都是叶子节点

结果: true

示例2：不同的树

步骤1: 比较根节点
p:  1        q:  1
   /              \
  2                2
值相同 ✓

步骤2: 递归比较左子树
p:  2        q:  null
左边有节点，右边为空 ✗

结果: false

代码实现

递归（DFS）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 情况1: 两个节点都为空 → 相同
        if (p == nullptr && q == nullptr) {
            return true;
        }

        // 情况2: 其中一个为空，另一个不为空 → 不同
        if (p == nullptr || q == nullptr) {
            return false;
        }

        // 情况3: 两个节点都不为空
        // 比较当前节点的值，并递归比较左右子树
        return p->val == q->val &&
               isSameTree(p->left, q->left) &&
               isSameTree(p->right, q->right);
    }
};

时间复杂度: O(min(m, n))，m 和 n 分别是两棵树的节点数，最多访问较小树的所有节点

空间复杂度: O(min(h1, h2))，递归栈深度，最坏情况下为树的高度

迭代（BFS）

使用队列同时遍历两棵树。

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> queue1, queue2;
        queue1.push(p);
        queue2.push(q);

        while (!queue1.empty() && !queue2.empty()) {
            TreeNode* node1 = queue1.front();
            queue1.pop();
            TreeNode* node2 = queue2.front();
            queue2.pop();

            // 两个节点都为空，继续
            if (node1 == nullptr && node2 == nullptr) {
                continue;
            }

            // 其中一个为空或值不同，返回 false
            if (node1 == nullptr || node2 == nullptr) {
                return false;
            }
            if (node1->val != node2->val) {
                return false;
            }

            // 将左右子节点加入队列
            queue1.push(node1->left);
            queue1.push(node1->right);
            queue2.push(node2->left);
            queue2.push(node2->right);
        }

        return true;
    }
};