LeetCode - 101 - 对称二叉树(symmetric-tree)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 101 - 对称二叉树(symmetric-tree)

Create by jsliang on 2019-6-14 08:21:33
Recently revised in 2019-6-14 08:56:26

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 LeetCode Submit | | 六 解题思路 |

二 前言

  • 难度:简单

  • 涉及知识:树、深度优先搜索、广度优先搜索

  • 题目地址:https://leetcode-cn.com/problems/symmetric-tree/

  • 题目内容

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

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

  3. 1

  4. / \

  5. 2 2

  6. / \ / \

  7. 3 4 4 3

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

  9. 1

  10. / \

  11. 2 2

  12. \ \

  13. 3 3

  14. 说明:

  15. 如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码

  1. var isSymmetric = function(root) {

  2. if (!root) {

  3. return true;

  4. }

  5. const leftTree = root.left;

  6. const rightTree = root.right;

  7. // 思路,将左侧树或者右侧数反过来遍历

  8. let leftErgodic = function(root) {

  9. if (!root) {

  10. return '!#'

  11. }

  12. return `${root.val}!${leftErgodic(root.left)}${leftErgodic(root.right)}`;

  13. }

  14. let rightErgodic = function(root) {

  15. if (!root) {

  16. return '!#'

  17. }

  18. return `${root.val}!${rightErgodic(root.right)}${rightErgodic(root.left)}`;

  19. }

  20. return leftErgodic(leftTree) === rightErgodic(rightTree);

  21. };

四 执行测试

  • 变量 root

  1. let root = {

  2. val: 1,

  3. left: {

  4. val: 2,

  5. left: { val: 3, left: null, right: null, },

  6. right: { val: 4, left: null, right: null, },

  7. },

  8. right: {

  9. val: 2,

  10. left: { val: 4, left: null, right: null, },

  11. right: { val: 3, left: null, right: null, }

  12. },

  13. }

  • 返回值 return

  1. true

五 LeetCode Submit

  1. Accepted

  2. 195/195 cases passed (88 ms)

  3. Your runtime beats 92.04 % of javascript submissions

  4. Your memory usage beats 5.15 % of javascript submissions (37 MB)

六 解题思路

首先,如果小伙伴有看过上一篇 100-相同的树(same-tree) 的攻略,应该知道破解树的算法有一个套路:

  1. let traverse = function(root) {

  2. // root 需要做什么?在这做。

  3. // 其他的不用 root 操心,抛给框架

  4. traverse(root.left);

  5. traverse(root.right);

  6. }

所以,在这里,我们需要做的,就是将除第一个节点外,它的左侧树和右侧树遍历出来。

然后,因为我们需要的是这个数是否是镜像二叉树(对称二叉树),那么我们就应该将左侧树从左到右遍历,将右侧数从右到左遍历,这样它们的顺序就会一致:

  1. const leftTree = root.left;

  2. const rightTree = root.right;

  3. let leftErgodic = function(root) {

  4. if (!root) {

  5. return '!#'

  6. }

  7. return `${root.val}!${leftErgodic(root.left)}${leftErgodic(root.right)}`;

  8. }

  9. let rightErgodic = function(root) {

  10. if (!root) {

  11. return '!#'

  12. }

  13. return `${root.val}!${rightErgodic(root.right)}${rightErgodic(root.left)}`;

  14. }

这样,我们就会得到两个字符串:

  1. 2!3!!#!#4!!#!#

  2. 2!3!!#!#4!!#!#

最后,我们返回它们的比较即可。


不折腾的前端,和咸鱼有什么区别!

LeetCode - 101 - 对称二叉树(symmetric-tree)

jsliang 会每天在公众号发表一篇文章,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构等等。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 101 - 对称二叉树(symmetric-tree)
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Black Box Society

The Black Box Society

Frank Pasquale / Harvard University Press / 2015-1-5 / USD 35.00

Every day, corporations are connecting the dots about our personal behavior—silently scrutinizing clues left behind by our work habits and Internet use. The data compiled and portraits created are inc......一起来看看 《The Black Box Society》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码