本篇图文是LSGO软件技术团队组织的 第二期基础算法(Leetcode)刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式,即选择了五个知识点(数组、链表、字符串、树、贪心算法),每个知识点选择了 三个简单、两个中等、一个困难 等级的题目,共计三十道题,利用三十天的时间完成这组刻意练习。
本次任务的知识点:树
树 是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由 n(n>0)
个有限节点组成的一个具有层次关系的集合。
把它叫做「树」是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
它具有以下的特点:
每个节点都只有有限个子节点或无子节点;
没有父节点的节点称为根节点;
每一个非根节点有且只有一个父节点;
除了根节点外,每个子节点可以分为多个不相交的子树;
树里面没有环路。
题号:101
难度:简单
https://leetcode-cn.com/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% 的用户
/**
* 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% 的用户
# 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% 的用户
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;
}
}
联系客服