TypeScript判断对称的二叉树方案详解

目录
  • 前言
  • 实现思路
  • 实现代码
  • 示例代码

前言

如果一颗二叉树和它的镜像一样，那么它就是对称的。实现一个函数用于判断一颗二叉树是否对称，你会怎么做？

本文将分享一种解决方案，欢迎各位感兴趣的开发者阅读本文。

实现思路

在上一篇文章二叉树的镜像中我们知道了此问题的解决方案是前序遍历，那么我们可以修改下前序遍历算法，父节点遍历后，先遍历它的右子节点，再遍历它的左子节点，我们把这种算法称为：对称前序遍历

如下图所示的两棵树，我们分别列举下两种遍历的结果：

  • 树A：

    • 前序遍历：8, 6, 5, 7, 6, 7, 5
    • 对称前序遍历：8, 6, 5, 7, 6, 7, 5
  • 树B：
    • 前序遍历：8, 6, 5, 7, 9, 7, 5
    • 对称前序遍历：8, 9, 5, 7, 6, 7, 5

经过对比后，我们发现树A的两种遍历方法得到的结果是一样的，那么它就是对称的；树B的结果不同，它就不是对称的。

如果有一颗不完全二叉树，它的所有节点都相同，他是对称的吗？

针对于这种情况，我们就需要将它缺省的null节点进行补齐了，补齐后的两种遍历结果为：

  • 前序遍历：7, 7, 7, null, null, 7, null, null, 7, 7, null, null, null
  • 对称前序遍历：7, 7, null, 7, null, null, 7, 7, null, null, 7, null, null

对比两个结果后，我们发现并不一样，那么它就不是对称的。

实现代码

有了思路后，接下来我们看下代码实现，如下所示：

  • 从树的根节点出发，递归比对它的左子节点和右子节点
  • 比对过程中：
    • 二者都到达叶子结点，代表这棵树是对称的
    • 任意一方到达叶子结点，代表这棵树不对称
    • 节点值不同，这棵树不对称
export function SymmetricBinaryTree(node: BinaryTreeNode | null): boolean {
  return isSymmetrical(node, node);
}
function isSymmetrical(
  node: BinaryTreeNode | null | undefined,
  cloneNode: BinaryTreeNode | null | undefined
): boolean {
  // 到达叶子节点，两者都为nul代表节点相同
  if (node == null && cloneNode == null) {
    return true;
  }
  // 任意一方到达叶子节点，代表节点不同
  if (node == null || cloneNode == null) {
    return false;
  }
  // 节点值不同
  if (node.key != cloneNode.key) {
    return false;
  }
  // 分别比对树的左子节点和右子节点
  return (
    isSymmetrical(node.left, cloneNode.right) &&
    isSymmetrical(node.right, cloneNode.left)
  );
}

接下来，我们以上个章节列举的例子为例，将其带入上述代码，验证下能否正确判断，如下所示：

const tree: BinaryTreeNode = {
  key: 8,
  left: {
    key: 6,
    left: { key: 5 },
    right: { key: 7 }
  },
  right: { key: 6, left: { key: 7 }, right: { key: 5 } }
};
const isSymmetric = SymmetricBinaryTree(tree);
console.log(tree, "是否为对称二叉树: ", isSymmetric);

示例代码

本文所用代码完整版请移步：

以上就是TypeScript实现对称的二叉树详解的详细内容，更多关于TypeScript 对称二叉树的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java 对称二叉树的判断

    1. 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 2. 解题思路 可以按照类似层次遍历,来判断是否是堆成二叉树: 首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同,以及左子树的右子树和右子树的左子树相同即可,然后采用递归一直判断下去. 3. 代码 public class isSymmetrical { public static void main(String[] args) { // 新建一棵二叉搜索

  • Python对称的二叉树多种思路实现方法

    对称二叉树的含义非常容易理解,左右子树关于根节点对称,具体来讲,对于一颗对称二叉树的每一颗子树,以穿过根节点的直线为对称轴,左边子树的左节点=右边子树的右节点,左边子树的右节点=左边子树的左节点.所以对称二叉树的定义是针对一棵树,而判断的操作是针对节点,这时可以采取由上到下的顺序,从根节点依次向下判断,只需要重复调用函数,不需要回溯. 题目:对称的二叉树题: 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的 解题思路一:先遍历右子节点再

  • PHP实现判断二叉树是否对称的方法

    本文实例讲述了PHP实现判断二叉树是否对称的方法.分享给大家供大家参考,具体如下: 问题 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 题解 递归判断二叉树两侧. 实现代码: <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ func

  • TypeScript判断对称的二叉树方案详解

    TypeScript判断对称的二叉树方案详解

    目录 前言 实现思路 实现代码 示例代码 前言 如果一颗二叉树和它的镜像一样,那么它就是对称的.实现一个函数用于判断一颗二叉树是否对称,你会怎么做? 本文将分享一种解决方案,欢迎各位感兴趣的开发者阅读本文. 实现思路 在上一篇文章二叉树的镜像中我们知道了此问题的解决方案是前序遍历,那么我们可以修改下前序遍历算法,父节点遍历后,先遍历它的右子节点,再遍历它的左子节点,我们把这种算法称为:对称前序遍历 如下图所示的两棵树,我们分别列举下两种遍历的结果: 树A: 前序遍历:8, 6, 5, 7, 6,

  • Android中图片压缩方案详解及源码下载

    Android中图片压缩方案详解及源码下载 图片的展示可以说在我们任何一个应用中都避免不了,可是大量的图片就会出现很多的问题,比如加载大图片或者多图时的OOM问题,可以移步到Android高效加载大图及多图避免程序OOM.还有一个问题就是图片的上传下载问题,往往我们都喜欢图片既清楚又占的内存小,也就是尽可能少的耗费我们的流量,这就是我今天所要讲述的问题:图片的压缩方案的详解. 1.质量压缩法 设置bitmap options属性,降低图片的质量,像素不会减少 第一个参数为需要压缩的bitmap图

  • MySQL 快速删除大量数据（千万级别）的几种实践方案详解

    笔者最近工作中遇见一个性能瓶颈问题,MySQL表,每天大概新增776万条记录,存储周期为7天,超过7天的数据需要在新增记录前老化.连续运行9天以后,删除一天的数据大概需要3个半小时(环境:128G, 32核,4T硬盘),而这是不能接受的.当然如果要整个表删除,毋庸置疑用 TRUNCATE TABLE就好. 最初的方案(因为未预料到删除会如此慢),代码如下(最简单和朴素的方法): delete from table_name where cnt_date <= target_date 后经过研究,

  • Java之单例模式实现方案详解

    单例模式是最常用到的设计模式之一,熟悉设计模式的朋友对单例模式都不会陌生.一般介绍单例模式的书籍都会提到 饿汉式 和 懒汉式 这两种实现方式.但是除了这两种方式,本文还会介绍其他几种实现单例的方式,让我们来一起看看吧. 简介 单例模式是一种常用的软件设计模式,其定义是单例对象的类只能允许一个实例存在. 许多时候整个系统只需要拥有一个的全局对象,这样有利于我们协调系统整体的行为.比如在某个服务器程序中,该服务器的配置信息存放在一个文件中,这些配置数据由一个单例对象统一读取,然后服务进程中的其他对象

  • JavaScript 中断请求几种方案详解

    目录 1 Promise 中断调用链 中断Promise 包装abort方法--仿照Axios的CancelToken 2 RXJS的unsubscribe方法 3 Axios的CancelToken 1 Promise Promise有一个缺点是一旦创建无法取消,所以本质上Promise是无法被终止的. 但是我们可以通过中断调用链或中断Promise来模拟请求的中断. 中断调用链 中断调用链就是在某一个then/catch执行之后,后续的链式调用(包括then,catch,finally)不再

  • Spring Boot实现数据访问计数器方案详解

    目录 1.数据访问计数器 2.代码实现 2.1.方案说明 2.2.代码 2.3.调用 1.数据访问计数器   在Spring Boot项目中,有时需要数据访问计数器.大致有下列三种情形: 1)纯计数:如登录的密码错误计数,超过门限N次,则表示计数器满,此时可进行下一步处理,如锁定该账户. 2)时间滑动窗口:设窗口宽度为T,如果窗口中尾帧时间与首帧时间差大于T,则表示计数器满.   例如使用redis缓存时,使用key查询redis中数据,如果有此key数据,则返回对象数据:如无此key数据,则查

  • Android WebView软键盘遮挡输入框方案详解

    Android WebView软键盘遮挡输入框方案详解

    目录 背景 纪实 方案 实现 总结 背景 笔者在使用 WebView 加载含有输入框的 H5 页面时,点击输入框后,输入框会被软键盘遮挡住,无法看到输入的内容,这很影响用户体验. 笔者想着这种业务场景比较常见,遂上网搜索一番,果不其然,有不少同志遇到这个问题,想来这个问题很好解决了.笔者一一尝试了同志们提供的解决方案,结果要不是没有作用,要不是效果不太满意,只好自己另辟蹊径了. 注:在笔者的业务场景中,App是全屏的,即没有顶部的系统栏,也没有底部的导航栏,所以笔者的解决方案,可能不适用于其他场

  • Spring处理@Async导致的循环依赖失败问题的方案详解

    Spring处理@Async导致的循环依赖失败问题的方案详解

    目录 简介 问题复现 原因分析 解决方案 方案1:懒加载 方案2:不让@Async的类有循环依赖 方案3:allowRawInjectionDespiteWrapping设置为true 为什么@Transactional不会导致失败 简介 说明 本文介绍SpringBoot中的@Async导致循环依赖失败的原因及其解决方案. 概述 我们知道,Spring解决了循环依赖问题,但Spring的异步(@Async)会使得循环依赖失败.本文将用实例来介绍其原因和解决方案. 问题复现 启动类 启动类添加@

  • Pulsar负载均衡原理及优化方案详解

    目录 前言 Pulsar 负载均衡原理 ThresholdShedder 原理 问题原因 优化方案 总结 前言 前段时间我们在升级 Pulsar 版本的时候发现升级后最后一个节点始终没有流量. 虽然对业务使用没有任何影响,但负载不均会导致资源的浪费. 和同事沟通后得知之前的升级也会出现这样的情况,最终还是人工调用 Pulsar 的 admin API 完成的负载均衡. 这个问题我尝试在 Google 和 Pulsar 社区都没有找到类似的,不知道是大家都没碰到还是很少升级集群. 我之前所在的公司

  • 前端JS图片懒加载原理方案详解

    目录 背景 原理 方案 方案一:img的loading属性设为“lazy” 使用方法 优点 兼容性 缺点 方案二:通过offsetTop来计算是否在可视区域内 优化 优点 缺点 方案三:通过getBoundingClientRect来计算是否在可视区域内 方案四:使用IntersectionObserver来判断是否在可视区域内 兼容性 优点 缺点 问题 布局抖动 响应式图片 SEO不友好 插件 背景 懒加载经常出现在前端面试中,是前端性能优化的常用技巧.懒加载也叫延迟加载,把非关键资源先不加载

随机推荐