100.相同的树

LeetCode LeetCode 树深度优先搜索广度优先搜索二叉树

发布时间 : 2000-01-10 01:00

字数:1.3k 阅读 :

评论:

100.相同的树

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 题解

递归比较节点

// 方法一：递归比较节点
// 对节点进行空和节点值是否相等的递归判断
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;
}

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