【原】刻意练习：LeetCode实战 -- Task20. 对称二叉树

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：树

树 是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由 n(n>0) 个有限节点组成的一个具有层次关系的集合。

把它叫做「树」是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

它具有以下的特点：

• 每个节点都只有有限个子节点或无子节点；

• 没有父节点的节点称为根节点；

• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树；

• 树里面没有环路。

---

题目

• 题号：101

• 难度：简单

• https:///problems/symmetric-tree/

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3


但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3


---

实现

第一种：采用递归的方法

• 执行结果：通过

• 执行用时：132 ms, 在所有 C# 提交中击败了 16.67% 的用户

• 内存消耗：25.1 MB, 在所有 C# 提交中击败了 5.17% 的用户

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */

//镜像对称的递归函数
public class Solution
{
    public bool IsSymmetric(TreeNode root)
    {
        return IsMirror(root, root);
    }
    private bool IsMirror(TreeNode t1, TreeNode t2)
    {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && IsMirror(t1.left, t2.right)
            && IsMirror(t1.right, t2.left);
    }
}


Python 语言

• 执行结果：通过

• 执行用时：48 ms, 在所有 Python3 提交中击败了 30.95% 的用户

• 内存消耗：13.7 MB, 在所有 Python3 提交中击败了 5.17% 的用户

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isMirror(root, root)

    def isMirror(self, t1: TreeNode, t2: TreeNode) -> bool:
        if t1 is None and t2 is None:
            return True
        if t1 is None or t2 is None:
            return False
        return t1.val == t2.val and self.isMirror(t1.left, t2.right) and self.isMirror(t1.right, t2.left)


第二种：采用队列的方法

思路：利用二叉树的层次遍历的方式来实现。

• 执行结果：通过

• 执行用时：112 ms, 在所有 C# 提交中击败了 70.93% 的用户

• 内存消耗：24.9 MB, 在所有 C# 提交中击败了 5.17% 的用户

public class Solution
{
    public bool IsSymmetric(TreeNode root)
    {
        if (root == null)
            return true;

        Queue<TreeNode> nodes = new Queue<TreeNode>();
        nodes.Enqueue(root.left);
        nodes.Enqueue(root.right);
        while (nodes.Count != 0)
        {
            TreeNode node1 = nodes.Dequeue();
            TreeNode node2 = nodes.Dequeue();

            if (node1 == null && node2 == null)
                continue;
            if (node1 == null || node2 == null)
                return false;
            if (node1.val != node2.val)
                return false;
            nodes.Enqueue(node1.left);
            nodes.Enqueue(node2.right);
            nodes.Enqueue(node1.right);
            nodes.Enqueue(node2.left);
        }
        return true;
    }
}


---