宏观视角下，如何精选「对称二叉树」问题的解决方案？

本文共计2055个文字，预计阅读时间需要9分钟。

题目描述：在牛客网上的JZ+58对称的二叉树，难度为困难。Tag：#剑指Offer#、#二叉树#、#层序遍历#、#递归#描述：请实现一个函数，用来判断一棵树是否对称。

题目描述

这是「牛客网」上的「JZ 58 对称的二叉树」，难度为「困难」。

Tag : 「剑指 Offer」、「二叉树」、「层序遍历」、「迭代」、「递归」

描述：

请实现一个函数，用来判断一棵二叉树是不是对称的。

注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

示例1

输入：{8,6,6,5,7,7,5}

返回值：true

示例2

输入：{8,6,9,5,7,7,5}

返回值：false

要求：

• 时间：1 s
• 空间：64 M

基本思想

首先要明确，题目所定义的 “对称” 是对每层而言，同时考虑空节点。

因此，如果我们使用常规的遍历方式进行检查的话，需要对空节点有所表示。

局部检查（层序遍历）

我们使用 ​​0x3f3f3f3f​​​ 作为无效值，并建立占位节点 ​​emptyNode​​​ 用来代指空节点（​​emptyNode.val = 0x3f3f3f3f​​）。

一个朴素的做法是：使用「层序遍历」的方式进行「逐层检查」，对于空节点使用 ​​emptyNode​​​ 进行代指，同时确保不递归 ​​emptyNode​​ 对应的子节点。