100.相同的树

LeetCode LeetCode 树 深度优先搜索 广度优先搜索 二叉树
发布时间 :
字数:1.8k 阅读 : 评论:
  1. 100.相同的树
    1. 100.1 题目
    2. 100.2 题解
      1. 方法一：递归比较节点
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：迭代比较节点（使用队列）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 100.3 代码
    4. 100.4 运行结果

100.相同的树

100.1 题目

给你两棵二叉树的根节点 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

100.2 题解

方法一：递归比较节点

思路

两棵树相同，当且仅当：根节点相同、左子树相同、右子树相同。这天然适合递归处理。

递归逻辑分三步：

  1. 判断两个节点是否同时为空，是则返回 true
  2. 判断是否只有一个为空，是则返回 false
  3. 比较节点值是否相等，并递归比较左右子树

举个例子：

树 p:    1        树 q:    1
        / \              / \
       2   3            2   3
  • 比较根节点：都是 1，相等
  • 递归比较左子树：都是节点 2，相等
  • 递归比较右子树：都是节点 3，相等
  • 返回 true

复杂度分析

  • 时间复杂度：O(min(m, n))，其中 m 和 n 分别是两棵树的节点数，最坏情况需要遍历较小的那棵树
  • 空间复杂度：O(min(m, n))，递归栈的深度取决于较小的树的高度

代码

// 方法一：递归比较节点
// 对节点进行空和节点值是否相等的递归判断
static bool IsSameTree1(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 IsSameTree1(p.left, q.left) && IsSameTree1(p.right, q.right);
}

方法二：迭代比较节点（使用队列）

思路

递归的本质是用系统栈保存状态，我们可以用显式的队列来模拟这一过程。

具体步骤：

  1. 将两棵树的根节点成对入队
  2. 每次从队列中取出两个节点进行比较
  3. 如果都为空则跳过；如果只有一个为空或值不相等则返回 false
  4. 将它们的左右子节点成对入队
  5. 当队列为空时，说明所有对应节点都相同

举个例子：

树 p:    1        树 q:    1
        / \              / \
       2   3            2   3

队列操作：
1. 入队：(p节点1, q节点1)
2. 出队比较：值都是1，相等 → 入队 (p.左2, q.左2), (p.右3, q.右3)
3. 出队比较：值都是2，相等 → 入队 (null, null), (null, null)
4. 出队比较：都是null，跳过
5. ... 最终返回 true

复杂度分析

  • 时间复杂度：O(min(m, n))，与递归方法相同
  • 空间复杂度：O(min(m, n))，队列中最多同时存储一层的节点对

代码

// 方法二：迭代比较节点（使用队列）
// 队列压入两个树的当前节点，弹出进行比较，再压入左右节点循环比较
static bool IsSameTree2(TreeNode p, TreeNode q)
{
    // 使用队列来进行迭代比较
    Queue<TreeNode> queue = new Queue<TreeNode>();

    // 将根节点 p 和 q 入队
    queue.Enqueue(p);
    queue.Enqueue(q);

    // 循环直到队列为空
    while (queue.Count > 0)
    {
        // 出队两个节点进行比较
        TreeNode nodeP = queue.Dequeue();
        TreeNode nodeQ = queue.Dequeue();

        // 如果两个节点都为空，则相同，继续下一轮迭代
        if (nodeP == null && nodeQ == null)
            continue;

        // 如果一个节点为空，另一个不为空，则不同，返回 false
        if (nodeP == null || nodeQ == null)
            return false;

        // 比较当前节点的值
        if (nodeP.val != nodeQ.val)
            return false;

        // 将左右子节点入队
        queue.Enqueue(nodeP.left);
        queue.Enqueue(nodeQ.left);
        queue.Enqueue(nodeP.right);
        queue.Enqueue(nodeQ.right);
    }

    // 所有节点比较完毕，相同
    return true;
}

100.3 代码

using System;
using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x)
    {
        val = x;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你两棵二叉树的根节点 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

        #endregion

        #region 测试

        // 示例 1
        TreeNode p1 = new TreeNode(1)
        {
            left = new TreeNode(2),
            right = new TreeNode(3)
        };
        TreeNode q1 = new TreeNode(1)
        {
            left = new TreeNode(2),
            right = new TreeNode(3)
        };
        bool result1 = IsSameTree1(p1, q1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        bool result1_2 = IsSameTree2(p1, q1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        TreeNode p2 = new TreeNode(1)
        {
            left = new TreeNode(2)
        };
        TreeNode q2 = new TreeNode(1)
        {
            right = new TreeNode(2)
        };
        bool result2 = IsSameTree1(p2, q2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        bool result2_2 = IsSameTree2(p2, q2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        TreeNode p3 = new TreeNode(1)
        {
            left = new TreeNode(2),
            right = new TreeNode(1)
        };
        TreeNode q3 = new TreeNode(1)
        {
            left = new TreeNode(1),
            right = new TreeNode(2)
        };
        bool result3 = IsSameTree1(p3, q3);
        Console.WriteLine($"示例3 方法1 输出：{result3}");
        bool result3_2 = IsSameTree2(p3, q3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归比较节点
    // 对节点进行空和节点值是否相等的递归判断
    static bool IsSameTree1(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 IsSameTree1(p.left, q.left) && IsSameTree1(p.right, q.right);
    }

    // 方法二：迭代比较节点（使用队列）
    // 队列压入两个树的当前节点，弹出进行比较，再压入左右节点循环比较
    static bool IsSameTree2(TreeNode p, TreeNode q)
    {
        // 使用队列来进行迭代比较
        Queue<TreeNode> queue = new Queue<TreeNode>();

        // 将根节点 p 和 q 入队
        queue.Enqueue(p);
        queue.Enqueue(q);

        // 循环直到队列为空
        while (queue.Count > 0)
        {
            // 出队两个节点进行比较
            TreeNode nodeP = queue.Dequeue();
            TreeNode nodeQ = queue.Dequeue();

            // 如果两个节点都为空，则相同，继续下一轮迭代
            if (nodeP == null && nodeQ == null)
                continue;

            // 如果一个节点为空，另一个不为空，则不同，返回 false
            if (nodeP == null || nodeQ == null)
                return false;

            // 比较当前节点的值
            if (nodeP.val != nodeQ.val)
                return false;

            // 将左右子节点入队
            queue.Enqueue(nodeP.left);
            queue.Enqueue(nodeQ.left);
            queue.Enqueue(nodeP.right);
            queue.Enqueue(nodeQ.right);
        }

        // 所有节点比较完毕，相同
        return true;
    }

    #endregion
}

100.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏