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

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

一 目录

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

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

二 前言

返回目录

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

例如,二叉树 [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

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

三 解题

返回目录

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

  • 解题代码
var isSymmetric = function(root) {
  if (!root) {
    return true;
  }
  const leftTree = root.left;
  const rightTree = root.right;
  // 思路,将左侧树或者右侧数反过来遍历
  let leftErgodic = function(root) {
    if (!root) {
      return '!#'
    }
    return `${root.val}!${leftErgodic(root.left)}${leftErgodic(root.right)}`;
  }
  let rightErgodic = function(root) {
    if (!root) {
      return '!#'
    }
    return `${root.val}!${rightErgodic(root.right)}${rightErgodic(root.left)}`;
  }
  return leftErgodic(leftTree) === rightErgodic(rightTree);
};

四 执行测试

返回目录

  • 变量 root
let root = {
  val: 1,
  left: {
    val: 2,
    left: { val: 3, left: null, right: null, },
    right: { val: 4, left: null, right: null, },
  },
  right: {
    val: 2,
    left: { val: 4, left: null, right: null, },
    right: { val: 3, left: null, right: null, }
  },
}
  • 返回值 return
true

五 LeetCode Submit

返回目录

√ Accepted
  √ 195/195 cases passed (88 ms)
  √ Your runtime beats 92.04 % of javascript submissions
  √ Your memory usage beats 5.15 % of javascript submissions (37 MB)

六 解题思路

返回目录

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

let traverse = function(root) {
  // root 需要做什么?在这做。
  // 其他的不用 root 操心,抛给框架
  traverse(root.left);
  traverse(root.right);
}

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

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

const leftTree = root.left;
const rightTree = root.right;
let leftErgodic = function(root) {
  if (!root) {
    return '!#'
  }
  return `${root.val}!${leftErgodic(root.left)}${leftErgodic(root.right)}`;
}
let rightErgodic = function(root) {
  if (!root) {
    return '!#'
  }
  return `${root.val}!${rightErgodic(root.right)}${rightErgodic(root.left)}`;
}

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

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

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


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

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

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

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

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-14 21:45:48

results matching ""

    No results matching ""