文章目录
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
}
}
思路
我们知道二叉树的深度优先遍历的方式有三种：前序遍历（root->left->right）、中序遍历(left->root->right)、后序遍历（left->right-root）,对于镜像二叉树来说，如果从中间画一个对称轴，实际上左右两边的节点是一样的，换个角度来说，就是刚好两边的遍历是反着的，如果我们采用前序遍历的方式遍历，那么反向的前序遍历和前序遍历的结果一样
如上图可知，如果我们能够构建出一个反向的对称的前序遍历方式，将其遍历结果与前序遍历的结果比较是否相等，那么就可以判断该二叉树是否是镜像的了
boolean isSymmetrical(TreeNode pRoot) {
return isSymmetrical(pRoot, pRoot);
}
boolean isSymmetrical(TreeNode root1,TreeNode root2){
if(root1 == null && root2 == null) return true;
if(root1 == null || root2 == null) return false;
if(root1.val != root2.val) return false;
return isSymmetrical(root1.left, root2.right) && isSymmetrical(root1.right,root2.left);
}
总结
从根节点开始，分别用前序遍历和对称前序遍历的方式进行遍历，同时还需要考虑到空节点的问题（两个都为空节点或者其中一个为空节点），本文采用的是前序遍历，先比较根节点的情况，再分别对左右节点分别进行比较
参考
《剑指offer纪念版》