【算法题】判断一颗二叉树是否对称

简介: 前端西瓜哥

大家好,我是前端西瓜哥。今天做一道比较基础的二叉树算法题。

题目

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

示例1:

image.png

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

示例 2:

image.png

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

本题 LeetCode 对应地址:

https://leetcode-cn.com/problems/symmetric-tree/

解法

如果你熟练写二叉树的先序、中序、后序遍历的递归写法套路,再看这题,可能一时不太能想到思路。

我一开始做这道题就是这样,我会将注意力放在一个节点上,尝试在上面写出花来。

但对这题来说并不受用,一开始或许可以对比根节点的左右子节点,但左右子节点的后继的子节点就不好取出来对比了。

对于这题,我们需要给递归函数,传入两个节点

function isSymmetric(root) {
  if (!root) return true;
  return compare(root.left, root.right);
};
function compare(left, right) {
  if (!left && !right) return true;
  if (!left || !right) return false;
  return left.val === right.val &&
    compare(left.left, right.right) &&
    compare(left.right, right.left);
}

compare 递归函数接收两个节点,如果这两个节点对称,返回 true,否则返回 false。

首先是 left 和 right 都为 null 的情况,属于对称,返回 null。

null 的情况需要在最前方判断,因为后面我们要使用 left.val 的语法,如果 left 是 null,会报错。

然后就是 left 或 right 其中一个为 null 另一个不为 null 的情况

因为前面的 if (!left && !right) return true; 如果不符合条件,代码往后走时,left 和 right 至少有一个不为 null。所以只要有 left 或 right 有一个 null,就说明一个为 null 一个不为 null,说明不对称,返回 false。

if (!left && !right) return true;
// 代码能运行到这里,说明 left 和 right 至少有一个为 null
if (!left || !right) return false;

如果你想更容易理解,可以改成这样子:

if (!left && !right) return true;
// 下面代码没有利用上面的条件判断
if (left && !right) return false;
if (!left && right) return false;

最后 left 和 right 都不为 null 的情况,我们需要对比以下节点

  • left 和 right
  • left.left 和 right.right
  • left.right 和 right.left

当这些都为 true 的话,递归函数就返回 true;否则返回 false。

这里的 && 操作符支持短路运行,当前面的条件不符合,后面的函数就不会执行,起到剪枝的效果。

LeetCode 官方递归解法的缺陷

我看了一下 LeetCode 的官方解法,发现它有个地方和我的不一样:

function isSymmetric(root) {
  return compare(root, root);
};
function compare(left, right) {
  // 实现同上
}

就是它是直接将 root 和 root 对比,我初一看,觉得挺优雅的,不需要像我一样写额外的 root 为空的判断。

但我很快发现了不妥的地方,那就是这种写法,在二叉树是对称的情况下,所有节点都要被访问两次

虽然从时间复杂度上来说,它也是 O(n) 的量级,但从实际情况是,LeetCode 官方解法在二叉树对称情况下,花费的时间为我的解法的两倍。

如果二叉树不对称,因为 && 运算的短路特性,耗时倒和我的解法没有太大区别。

我是前端西瓜哥,分享前端和算法知识,欢迎关注我。

相关文章
|
18天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
21天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
45 5
|
24天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
27 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
27 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
6月前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
38 0
|
6月前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
53 0
|
2月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0
|
4月前
|
算法 JavaScript 前端开发
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
300 1