其他
动画：面试必刷之对称的二叉树
点击蓝色 “小鹿动画学编程” 关注我哦!
加个 “星标” ，每天一篇动画喂饱你！
作者 | 小鹿
来源 | 小鹿动画学编程
题目
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
如图：
问题分析
仔细观察上图的对称二叉树，我们可以尝试着从中间线的左边和右边做一个对比，我们先打算用递归能不能解决，嗯，可以，但是递归的前提我们要搞明白下面所说的一种思路。
我们要想到遍历，其中，前序遍历的遍历规则是根、左、右。我们这时候灵机一动，我们对于对称二叉树来说，我们把规则变一下，变成根、右、左。如果此时是对称二叉树的话，这两种遍历的结果是相等的。否则，则不是对称二叉树。
PS：但是有种情况除外，尽管不是对称二叉树，遍历的结果也是相同的，节点缺失的情况。如下图：
动画实现
解决思路
首先，传入二叉树，判断传入的二叉树是否为空节点。
1const isSymmetrical = (root)=>{
2 // 判断根节点是否为空
3 if(root == null){
4 return true;
5 }
6 return Symmetric(root.left,root.right);
7}然后开始传入一个函数，对比对称的节点值是否相同，但是我们要想到如果节点为空的情况。
如果两个节点同时为空，我们判定为它是对称的节点。如果其中一个为空其中一个不为空，则两个节点不对称。
1 // 判断左右子树是否为空
2 if(left == null && right == null){
3 return true;
4 }
5
6 // 其中一个子节点是空
7 if(left == null || right == null){
8 return false;
9 }如果两个对称节点不为空的话，我们就比较两个对称节点的值是否相同。
1 // 判断两个节点的值是否相同
2 if(left.data == right.data){
3 return true;
4 }然后我们开始对剩下的节点进行递归遍历判断是否为对称节点。
1// 递归判断
2 return Symmetric(left.left,right.right) && Symmetric(left.right,right.left);代码实现
JavaScript
Java
Python
测试用例
对称二叉树、不对称二叉树（结点数量不对称、结点结构不对称） —— 普通测试 所有结点值都相同的二叉树 —— 特殊测试 空二叉树 —— 输入测试
「小鹿动画学编程」用动画的形式和你分享技术！
长按识别二维码关注