【剑指 の 精选】从宏观角度看「对称二叉树」问题（剑指玄天）

【剑指 の 精选】从宏观角度看「对称二叉树」问题（剑指玄天）

题目描述

这是「牛客网」上的「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​​ 对应的子节点。

具体做法如下：

起始时，将 ​​root​​ 节点入队；从队列中取出节点，检查节点是否为 ​​emptyNode​​ 节点来决定是否继续入队：

当不是 ​​emptyNode​​​ 节点时，将其左/右儿子进行入队，如果没有左/右儿子，则用 ​​emptyNode​​ 代替入队；当是 ​​emptyNode​​ 节点时，则忽略；

在进行流程 的同时使用「临时列表」记录当前层的信息，并检查当前层是否符合 “对称” 要求；循环流程 和 ，直到整个队列为空。

Java 代码：

import java.util.*;class Solution { int INF = 0x3f3f3f3f; TreeNode emptyNode = new TreeNode(INF); boolean isSymmetrical(TreeNode root) { if (root == null) return true; Deque d = new ArrayDeque<>(); d.add(root); while (!d.isEmpty()) { // 每次循环都将下一层拓展完并存到「队列」中 // 同时将该层节点值依次存入到「临时列表」中 int size = d.size(); List list = new ArrayList<>(); while (size-- > 0) { TreeNode poll = d.pollFirst(); if (!poll.equals(emptyNode)) { d.addLast(poll.left != null ? poll.left : emptyNode); d.addLast(poll.right != null ? poll.right : emptyNode); } list.add(poll.val); } // 每一层拓展完后，检查一下存放当前层的该层是否符合「对称」要求 if (!check(list)) return false; } return true; } // 使用「双指针」检查某层是否符合「对称」要求 boolean check(List list) { int l = 0, r = list.size() - 1; while (l < r) { if (!list.get(l).equals(list.get(r))) return false; l++; r--; } return true; }}

Python 3 代码：

from collections import dequefrom math import infclass Solution: emptyNode = TreeNode(inf) def isSymmetrical(self, root): if root is None: return True d = deque([]) d.append(root) while d: # 每次循环都将下一层拓展完并存到「队列」中 # 同时将该层节点值依次存入到「临时列表」中 size = len(d) lt = [] while size > 0: poll = d.popleft() if poll != self.emptyNode: d.append(poll.left if poll.left is not None else self.emptyNode) d.append(poll.right if poll.right is not None else self.emptyNode) size -= 1 lt.append(poll.val) # 每一层拓展完后，检查一下存放当前层的该层是否符合「对称」要求 if not self.check(lt): return False return True def check(self, lt): # 使用「双指针」检查某层是否符合「对称」要求 l, r = 0, len(lt) - 1 while l < r: if lt[l] != lt[r]: return False l += 1 r -= 1 return True

时间复杂度：在层序遍历过程中，每个节点最多入队一次，同时在​​check​​ 检查对称性过程中，每层只会被检查一次。复杂度为 O(n)空间复杂度：O(n)

整体检查（递归）

在「层序遍历」解法中，我们利用了 “对称” 定义对每层进行检查。

本质上这是利用 “对称” 定义进行多次「局部」检查。

事实上，我们还可以利用 “对称” 定义在「整体」层面上进行检查。

我们如何定义两棵子树 ​​a​​​ 和 ​​b​​ 是否 “对称” ？

当且仅当两棵子树符合如下要求时，满足 “对称” 要求：

两棵子树根节点值相同；两颗子树的左右子树分别对称，包括：

​​a​​​ 树的左子树与 ​​b​​ 树的右子树相应位置的值相等​​a​​​ 树的右子树与 ​​b​​ 树的左子树相应位置的值相等

具体的，我们可以设计一个递归函数 ​​check​​​ ，传入待检测的两颗子树的头结点 ​​a​​​ 和 ​​b​​​（对于本题都传入 ​​root​​ 即可），在单次查询中有如下显而易见的判断子树是否 “对称” 的 Base Case：

​​a​​​ 和 ​​b​​ 均为空节点：符合 “对称” 要求；​​a​​​ 和 ​​b​​ 其中一个节点为空，不符合  “对称” 要求；​​a​​​ 和 ​​b​​ 值不相等，不符合  “对称” 要求；

其他情况，我们则要分别检查 ​​a​​​ 和 ​​b​​​ 的左右节点是否 “对称” ，即递归调用 ​​check(a.left, b.right)​​​ 和 ​​check(a.right, b.left)​​。

Java 代码：

class Solution { public boolean isSymmetrical(TreeNode root) { return check(root, root); } boolean check(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; if (a.val != b.val) return false; return check(a.left, b.right) && check(a.right, b.left); }}

Python 3 代码：

class Solution: def isSymmetrical(self, root): return self.check(root, root) def check(self, a, b): if a is None and b is None: return True elif a is None or b is None: return False if a.val != b.val: return False return self.check(a.left, b.right) and self.check(a.right, b.left)

时间复杂度：每个节点只会被访问一次。复杂度为 O(n)空间复杂度：忽略递归带来的额外空间开销。复杂度为 O(1)

总结

上述两种解法不仅仅是实现上的不同，更多的是检查 “出发点” 的不同：

解法一：利用「层序遍历」的方式，以 “层” 为单位进行 “对称” 检查；解法二：利用「递归树展开」的方式，以 “子树” 为单位进行 “对称” 检查。

当我们从整体层面出发考虑时，配合递归，往往能写出比常规做法要简洁得多的代码。

建议大家加深对「局部」和「整体」两种不同出发点的理解。

最后

这是我们「剑指 の 精选」系列文章的第 ​​58​​ 篇，系列开始于 2021/07/01。

该系列会将「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。