TypeScript获取二叉树的镜像实例

目录
  • 前言
  • 思路分析
  • 实现代码

前言

给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文。

思路分析

当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的。那么我们就可以依据照镜子的经验画出它的镜像了,如下所示:

  • 镜像前后的两棵树根节点相同
  • 镜像后的树与镜像前相比:它们的左、右子节点交换了位置

通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后,就得到了树的镜像。

对树的遍历不了解的开发者,请移步我的另一篇文章:先序遍历

实现代码

想清楚思路后,我们就可以很顺利的写出代码了,如下所示:

export function MirrorImageOfTree(node: BinaryTreeNode | null): void {
  if (node == null) return;
  if (node.left == null && node.right == null) return;
  // 交换左右子节点
  const temp = node.left;
  node.left = node.right;
  node.right = temp;
  if (node.left) {
    MirrorImageOfTree(node.left);
  }
  if (node.right) {
    MirrorImageOfTree(node.right);
  }
}

完整代码请移步:MirrorImageOfTree.ts

我们将文章开头所讲的例子代入上述代码来测试下,如下所示:

const tree: BinaryTreeNode = {
  key: 8,
  left: {
    key: 5,
    left: { key: 3 },
    right: { key: 7 }
  },
  right: { key: 18, left: { key: 13 }, right: { key: 22 } }
};
MirrorImageOfTree(null);
console.log("镜像后的树", tree);

完整代码请移步:mirrorImage-test.ts

以上就是TypeScript获取二叉树的镜像实例的详细内容,更多关于TypeScript获取二叉树镜像的资料请关注我们其它相关文章!

(0)

相关推荐

  • TypeScript 内置高级类型编程示例

    目录 TypeScript 类型编程 TypeScript 内置高级类型 Pick<Type, Keys> Exclude<UnionType, ExcludedMembers> ReturnType<Type> 更多类型体操学习 TypeScript 类型编程 TypeScript 的类型系统,最基本的是简单对应 JavaScript 的 基本类型,比如 string.number.boolean 等,然后是新增的 tuple.enum.复合类型.交叉类型.索引类型等

  • TypeScript实用技巧 Nominal Typing名义类型详解

    目录 Nominal Typing(名义类型) 概念解析 拓展应用 在Vue中的应用 Nominal Typing(名义类型) 概念解析 意思是给一个类型附加上一个“名义”,从而防止结构类型在某些情况下由于类型结构相似而被错用.假设有如下代码: interface Vector2D { x: number, y: number }; interface Vector3D { x: number, y: number, z: number }; function calc(vector: Vect

  • 前端算法之TypeScript包含min函数的栈实例详解

    目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我

  • TypeScript数组实现栈与对象实现栈的区别详解

    目录 前言 数组实现栈 实现思路 实现代码 编写测试代码 对象实现栈 实现代码 编写测试代码 二者的区别 十进制转二进制 前言 栈作为一种数据结构,它可以应用在很多地方,当你需要经常获取刚存放进去的数据时,那么栈这种数据结构将是你的首选. 栈的实现方式一般有两种:数组实现和对象实现,这两种实现方式最终实现的功能都是一样的,但是在性能上却有着很大的差别. 本文将详细讲解这两种实现方式的差异并用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文. 数组实现栈 本文讲解的是栈用代码的实现,如

  • 详解Anyscript开发指南绕过typescript类型检查

    目录 前言 场景设定 解决方法 注释忽略 场景用例 类型断言 场景用例 泛型转换 场景用例 总结 前言 随着越来越多的前端项目采用 typescript 来开发,越来越多前端开发者会接触.使用这门语言.它是前端项目工程化的一个重要帮手,结合 vscode 编辑器,给予了前端开发者更严谨.高效的编码体验.但同时,严格的类型检查也会使部分开发者的编码效率有所降低,将时间花费在解决类型冲突.类型不匹配上,从而导致望而却步,迟迟不敢上手. 本文描述了几种绕过 typescript 类型检查的方法,帮助t

  • TypeScript获取二叉树的镜像实例

    目录 前言 思路分析 实现代码 前言 给定一颗二叉树,如何获取它的镜像?本文将跟大家分享这个问题的解决方案,欢迎各位感兴趣的开发者阅读本文. 思路分析 当我们把一张写有文字的纸放在镜子前面,你看到的内容正好与你写的内容是相反的.那么我们就可以依据照镜子的经验画出它的镜像了,如下所示: 镜像前后的两棵树根节点相同 镜像后的树与镜像前相比:它们的左.右子节点交换了位置 通过观察后,我们就得出了一颗树的镜像过程:先序遍历这棵树的每个节点,如果遍历到的节点有子节点,就交换它的两个子节点.当交换完所有非叶

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • C++ 二叉树的镜像实例详解

    二叉树的镜像:将一个二叉树的左右子树,调换位置.即下图的形式: 递归的思想是: 从根节点的左右子树进行交换,然后以根节点的左子树为根节点,而后以根节点的右结点为根节点,进行左右子树交换.遇到空节点或叶节点直接返回.下面求二叉树镜像的函数代码实现: template<class T> void MirroTree(TreeNode<T> * root) { if (root == NULL) return; if (root->_left == NULL &&

  • PHP获取二叉树镜像的方法

    本文实例讲述了PHP获取二叉树镜像的方法.分享给大家供大家参考,具体如下: 问题 操作给定的二叉树,将其变换为源二叉树的镜像. 解决思路 翻转二叉树,有递归和非递归两种方式,非递归就是使用队列. 实现代码 <?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function Mirror(&$

  • Java编程求二叉树的镜像两种方法介绍

    给出一棵二叉树,求它的镜像,如下图:右边是二叉树是左边二叉树的镜像. 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤.这两棵树的根节点相同,但他们的左右两个子节点交换了位置.因此我们不妨先在树中交换根节点的两个子节点,就得到了下面一幅图中的第二颗树 解法1(递归) 思路1:如果当前节点为空,返回,否则交换该节点的左右节点,递归的对其左右节点进行交换处理. /*class TreeNode{ int val; TreeNode left=null; TreeNode right=null;

  • Python二叉树的镜像转换实现方法示例

    本文实例讲述了Python二叉树的镜像转换实现方法.分享给大家供大家参考,具体如下: 问题描述 操作给定的二叉树,将其变换为源二叉树的镜像. 思路描述 1. 代码比文字更直观 2. 文字描述:新建一个二叉树,利用递归法,将源二叉树上的左节点赋值到新二叉树的右节点,将源二叉树上的右节点赋值到新二叉树的左节点. Python代码 # 方式1:生成新的镜像二叉树 def getMirrorBST(self, root): if root == None: return newTree = treeNo

  • php下载远程大文件(获取远程文件大小)的实例

    废话不多说,直接上代码 <?php // 暂不支持断点续传 // $url = 'http://www.mytest.com/debian.iso'; 不知道为何获取本地文件大小为0 $url = 'http://192.168.8.93/download/vm-672/18/0.vmdk'; $file = basename($url); $header = get_headers($url, 1); $size = $header['Content-Length']; $fp = fopen

  • IOS 获取APP 版本号的实例详解

    IOS 获取APP 版本号的实例详解 看代码的时候看到一句,用于获取.plist文件的版本号 labelVersion.text = [NSString stringWithFormat:@"v%@", [[NSBundle mainBundle] objectForInfoDictionaryKey:(NSString*)kCFBundleVersionKey]]; 比较感兴趣的是后面的参数 kcFBundleVersionKey ,竟然是CFBundle.h已经定于好的属性,下面有

  • python爬虫_自动获取seebug的poc实例

    简单的写了一个爬取www.seebug.org上poc的小玩意儿~ 首先我们进行一定的抓包分析 我们遇到的第一个问题就是seebug需要登录才能进行下载,这个很好处理,只需要抓取返回值200的页面,将我们的headers信息复制下来就行了 (这里我就不放上我的headers信息了,不过headers里需要修改和注意的内容会在下文讲清楚) headers = { 'Host':******, 'Connection':'close', 'Accept':******, 'User-Agent':*

  • Python3编程实现获取阿里云ECS实例及监控的方法

    本文实例讲述了Python3编程实现获取阿里云ECS实例及监控的方法.分享给大家供大家参考,具体如下: #!/usr/bin/env python3.5 # -*- coding:utf8 -*- try: import httplib except ImportError: import http.client as httplib import sys,datetime import urllib import urllib.request import urllib.error impor

随机推荐