关于leetcode:Leetcode-题解系列-对称二叉树递归

本专题旨在分享刷Leecode过程发现的一些思路乏味或者有价值的题目。【当然是基于js进行解答】。

递归算法始终是leetcode 中等难度习题的重点类型之一,所以关键性显而易见。

题目相干

  • 原题地址: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
  • 题目形容:

    请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
    例如,二叉树 [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

Tips

思考某些同学可能比拟少用js来刷leetcode,咱们在这里简略介绍下,对于树类型的数据输出,在js里的示意。 形如上题中的内容,给定二叉树的输出,其实并非一个数组,而应该是如下所示: 每个节点是一个object:

 const root = {
      val: 3,
      left: { // left示意以后节点的左侧子节点
        val: 9,
        left: null, // 对照上图能够看到 节点9没有左右子节点
        right: null,
      },
      right: {
        val: 20,
        left: {
          val: 15, // 对照上图能够看到 节点15没有左右子节点
          left: null, 
          right: null,
        }, 
        right: {
          val: 7, // 对照上图能够看到 节点7没有左右子节点
          left: null, 
          right: null,
        },
      }
    }

思路解析

首先这道题是显著的递归类题目, 而递归类的题目个别就是以下几个步骤:

  1. 提取递归局部的逻辑
  2. 判断边界条件

  • 首先整体的逻辑上, 要断定一棵树是镜像二叉树的话,必定是要从根节点的左右节点开始进行比照,在遍历过程遇到的每一组节点(用L和R示意),都要满足L的左节点 = R的右节点 且 L的右节点 = R的左节点 因为会递归比拟,所以这里相等其实就只有是val值相等:
  • 其次是思考边界条件

    1. 如果初始是一颗空的树,那间接返回后果,也算对称;
    2. 同步比对时,在任意一步,只有呈现不满足L的左节点 = R的右节点 且 L的右节点,= R的左节点 ,则提前结束,返回false;
    3. 如果可能比对到两边同时完结,那么阐明是对称树,返回true;

那么依照前文说的,先写出递归局部的逻辑:

    var recuCompare = function (L, R) {
        if(!L && !R) { // 阐明同时比对同时完结 或者是两边均无该子节点
            return true;
        }
        if(!L || !R || L.val !== R.val ) { // 扣除第一种状况 那么!L 或者 !R阐明左右不同时完结,也就是呈现不对称
            return false;
        }
        return recuCompare(L.left, R.right) && recuCompare(L.right, R.left); // 持续往下比对
    }

那么补上递归起始条件局部,残缺代码就能够得出了。

残缺代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) {return true};
    return recuCompare(root.left, root.right)
};
var recuCompare = function (L, R) {
    if(!L && !R) {
        return true;
    }
    if(!L || !R || L.val !== R.val )  {
        return false;
    }
    return recuCompare(L.left, R.right) && recuCompare(L.right, R.left);
}

有没有发现,递归类题目最初都是代码写进去后不长,然而了解比拟吃力,所以更须要本人尝试着去抓逻辑重点。

很倡议大家在看完之后,本人手写一次代码跑跑看
很倡议大家在看完之后,本人手写一次代码跑跑看
很倡议大家在看完之后,本人手写一次代码跑跑看

因为很多边界条件的写法和细节,其实才是调试过程中最常常出bug的。

另外,大家能够利用本题的思路,去试着解一下 这道递归回溯的题目–树的子结构 从而坚固所学 https://leetcode-cn.com/probl…

那么,简简单单一道题又搞定了!

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年50元

阿里云限时活动-2核2G-5M带宽-60G SSD-1000G月流量 ,特惠价99元/年(原价1234.2元/年,可以直接买3年),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据