题目:
请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
思路:
对称的特性就是当前节点的左子节点和右子节点一定是相等的,左子节点的左右节点和右子节点左右节点对称相等.
代码:
public class IsSymmetrical
{
/**
* 1.对称的特称当前节点的左右节点相同,左右节点的子节点相互对称
* @param pRoot
* @return
*/
public boolean isSymmetrical(TreeNode pRoot){
if(pRoot == null)
return false;
return isSymmetrical(pRoot.left,pRoot.right);
}
private boolean isSymmetrical(TreeNode left,TreeNode right){
//如果两个左右节点同时为空,返回true
if(left==null && right==null){
return true;
}
//如果两个节点一个为空一个不为空返回false
//代码到了这个阶段说明左右子树同时为空的可能性已经判断完了
//如果一方出现null,直接返回false
if(left==null || right==null){
return false;
}
//如果当个节点值相等且子节点成对称形状,返回true
return (left.val == right.val) &&
isSymmetrical(left.left,left.right) &&
isSymmetrical(left.right,left.left);
}
}