动画：面试必刷之对称的二叉树

题目

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

如图：

问题分析

仔细观察上图的对称二叉树，我们可以尝试着从中间线的左边和右边做一个对比，我们先打算用递归能不能解决，嗯，可以，但是递归的前提我们要搞明白下面所说的一种思路。

我们要想到遍历，其中，前序遍历的遍历规则是根、左、右。我们这时候灵机一动，我们对于对称二叉树来说，我们把规则变一下，变成根、右、左。如果此时是对称二叉树的话，这两种遍历的结果是相等的。否则，则不是对称二叉树。

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    }56    // 其中一个子节点是空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

测试用例

对称二叉树、不对称二叉树（结点数量不对称、结点结构不对称） —— 普通测试
所有结点值都相同的二叉树 —— 特殊测试
空二叉树 —— 输入测试

更多相关文章

随机推荐