共计 2939 个字符，预计需要花费 8 分钟才能阅读完成。
题目形容
这是「牛客网」上的 「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节点时，则疏忽；
- 在进行流程 的同时应用「长期列表」记录以后层的信息，并查看以后层是否合乎“对称”要求；
- 循环流程 和，直到整个队列为空。
代码：
import java.util.*;
class Solution {
int INF = 0x3f3f3f3f;
TreeNode emptyNode = new TreeNode(INF);
boolean isSymmetrical(TreeNode root) {if (root == null) return true;
Deque<TreeNode> d = new ArrayDeque<>();
d.add(root);
while (!d.isEmpty()) {
// 每次循环都将下一层拓展完并存到「队列」中
// 同时将该层节点值顺次存入到「长期列表」中
int size = d.size();
List<Integer> 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<Integer> 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;
}
}
- 工夫复杂度：在层序遍历过程中，每个节点最多入队一次，同时在
check查看对称性过程中，每层只会被查看一次。复杂度为 - 空间复杂度：
整体查看（递归）
在「层序遍历」解法中，咱们利用了“对称”定义对每层进行查看。
实质上这是利用“对称”定义进行屡次「部分」查看。
事实上，咱们还能够利用“对称”定义在「整体」层面上进行查看。
咱们如何定义两棵子树 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)。
代码：
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);
}
}
- 工夫复杂度：每个节点只会被拜访一次。复杂度为
- 空间复杂度：
总结
上述两种解法不仅仅是实现上的不同，更多的是查看“出发点”的不同：
- 解法一：利用「层序遍历」的形式，以“层”为单位进行“对称”查看；
- 解法二：利用「递归树开展」的形式，以“子树”为单位进行“对称”查看。
当咱们从整体层面登程思考时，配合递归，往往能写出比惯例做法要简洁得多的代码。
倡议大家加深对「部分」和「整体」两种不同出发点的了解。
最初
这是咱们「剑指 の 精选」系列文章的第 58 篇，系列开始于 2021/07/01。
该系列会将「剑指 Offer」中比拟经典而又不过时的题目都讲一遍。
在提供谋求「证实」&「思路」的同时，提供最为简洁的代码。
欢送关注，交个敌人 (`・ ω ・´)