101.对称二叉树

LeetCode LeetCode 树 深度优先搜索 广度优先搜索 二叉树
发布时间 :
字数:1.7k 阅读 : 评论:
  1. 101.对称二叉树
    1. 100.1 题目
    2. 100.2 题解
      1. 递归
      2. 迭代
    3. 100.3 代码
    4. 100.4 运行结果

101.对称二叉树

100.1 题目

给你一个二叉树的根节点 root，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

100.2 题解

递归

// 方法一：递归
// 首先检查左右子节点是否为空，如果均为空，则认为是对称的。
// 然后，检查左右子节点是否有一个为空，如果是，则认为不对称。
// 接下来，比较左右子节点的值是否相等，如果不相等，则认为不对称。
// 最后，递归地判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点是否镜像对称。
static bool IsSymmetricRecursive(TreeNode root)
{
    // 如果根节点为空，认为是对称的
    if (root == null) return true;

    // 调用辅助方法判断左右子树是否镜像对称
    return IsMirror(root.left, root.right);
}

// 判断两棵树是否镜像对称的辅助递归方法
static bool IsMirror(TreeNode left, TreeNode right)
{
    // 如果左右子节点均为空，认为是镜像对称的
    if (left == null && right == null) return true;

    // 如果左右子节点其中一个为空，另一个不为空，认为不对称
    if (left == null || right == null) return false;

    // 如果左右子节点的值不相等，认为不对称
    if (left.val != right.val) return false;

    // 递归地判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点是否镜像对称
    return IsMirror(left.left, right.right) && IsMirror(left.right, right.left);
}

迭代

// 方法二：迭代
// 使用迭代方法结合队列 判断二叉树是否对称
static bool IsSymmetricIterative(TreeNode root)
{
    // 使用队列进行层序遍历，同时比较每一层是否镜像对称
    Queue<TreeNode> queue = new Queue<TreeNode>();

    // 将根节点入队两次，因为初始时整个树就是对称的
    queue.Enqueue(root);
    queue.Enqueue(root);

    // 循环处理队列中的节点
    while (queue.Count > 0)
    {
        // 从队列中取出两个节点进行比较
        TreeNode t1 = queue.Dequeue();
        TreeNode t2 = queue.Dequeue();

        // 如果两个节点均为空，继续下一轮循环
        if (t1 == null && t2 == null) continue;

        // 如果两个节点中有一个为空，说明不对称，返回 false
        if (t1 == null || t2 == null) return false;

        // 如果两个节点的值不相等，说明不对称，返回 false
        if (t1.val != t2.val) return false;

        // 将 t1 的左子树和 t2 的右子树入队，以便后续比较
        queue.Enqueue(t1.left);
        queue.Enqueue(t2.right);

        // 将 t1 的右子树和 t2 的左子树入队，以便后续比较
        queue.Enqueue(t1.right);
        queue.Enqueue(t2.left);
    }

    // 如果循环结束，说明整个二叉树是对称的
    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 val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

        // 给你一个二叉树的根节点 root ， 检查它是否轴对称。
        // 示例 1：
        // 输入：root = [1,2,2,3,4,4,3]
        // 输出：true

        // 示例 2：
        // 输入：root = [1,2,2,null,3,null,3]
        // 输出：false

        // 提示：
        // 树中节点数目在范围 [1, 1000] 内
        // -100 <= Node.val <= 100

        #endregion

        #region 测试

        // 示例 1
        TreeNode root1 = new TreeNode(1,
            new TreeNode(2, new TreeNode(3), new TreeNode(4)),
            new TreeNode(2, new TreeNode(4), new TreeNode(3)));
        bool result1 = IsSymmetricRecursive(root1);
        Console.WriteLine($"示例1 递归 方法 输出：{result1}");
        bool result1_2 = IsSymmetricIterative(root1);
        Console.WriteLine($"示例1 迭代 方法 输出：{result1_2}");

        // 示例 2
        TreeNode root2 = new TreeNode(1,
            new TreeNode(2, null, new TreeNode(3)),
            new TreeNode(2, null, new TreeNode(3)));
        bool result2 = IsSymmetricRecursive(root2);
        Console.WriteLine($"示例2 递归 方法 输出：{result2}");
        bool result2_2 = IsSymmetricIterative(root2);
        Console.WriteLine($"示例2 迭代 方法 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：递归
    // 首先检查左右子节点是否为空，如果均为空，则认为是对称的。
    // 然后，检查左右子节点是否有一个为空，如果是，则认为不对称。
    // 接下来，比较左右子节点的值是否相等，如果不相等，则认为不对称。
    // 最后，递归地判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点是否镜像对称。
    static bool IsSymmetricRecursive(TreeNode root)
    {
        // 如果根节点为空，认为是对称的
        if (root == null) return true;

        // 调用辅助方法判断左右子树是否镜像对称
        return IsMirror(root.left, root.right);
    }

    // 判断两棵树是否镜像对称的辅助递归方法
    static bool IsMirror(TreeNode left, TreeNode right)
    {
        // 如果左右子节点均为空，认为是镜像对称的
        if (left == null && right == null) return true;

        // 如果左右子节点其中一个为空，另一个不为空，认为不对称
        if (left == null || right == null) return false;

        // 如果左右子节点的值不相等，认为不对称
        if (left.val != right.val) return false;

        // 递归地判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点是否镜像对称
        return IsMirror(left.left, right.right) && IsMirror(left.right, right.left);
    }


    // 方法二：迭代
    // 使用迭代方法结合队列 判断二叉树是否对称
    static bool IsSymmetricIterative(TreeNode root)
    {
        // 使用队列进行层序遍历，同时比较每一层是否镜像对称
        Queue<TreeNode> queue = new Queue<TreeNode>();

        // 将根节点入队两次，因为初始时整个树就是对称的
        queue.Enqueue(root);
        queue.Enqueue(root);

        // 循环处理队列中的节点
        while (queue.Count > 0)
        {
            // 从队列中取出两个节点进行比较
            TreeNode t1 = queue.Dequeue();
            TreeNode t2 = queue.Dequeue();

            // 如果两个节点均为空，继续下一轮循环
            if (t1 == null && t2 == null) continue;

            // 如果两个节点中有一个为空，说明不对称，返回 false
            if (t1 == null || t2 == null) return false;

            // 如果两个节点的值不相等，说明不对称，返回 false
            if (t1.val != t2.val) return false;

            // 将 t1 的左子树和 t2 的右子树入队，以便后续比较
            queue.Enqueue(t1.left);
            queue.Enqueue(t2.right);

            // 将 t1 的右子树和 t2 的左子树入队，以便后续比较
            queue.Enqueue(t1.right);
            queue.Enqueue(t2.left);
        }

        // 如果循环结束，说明整个二叉树是对称的
        return true;
    }


    #endregion
}

100.4 运行结果

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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏