给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
image.png
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
image.png
递归
class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null||isSymmetric(root.left,root.right);
}
public boolean isSymmetric(TreeNode left,TreeNode right){
if(left==null||right==null){
return left==right;
}
if(left.val!=right.val){
return false;
}
return isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
}
}
迭代思路
对左子树进行先序遍历，先将左子树节点加入栈，在弹出，之后把右孩子加入栈中，左孩子加入栈中，而对于右子树节点加入栈，再弹出，之后把左孩子加入栈中，有孩子加入栈中，分别对左右子树遍历节点，进行比较
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
TreeNode left=root.left;
TreeNode right=root.right;
Stack<TreeNode> s1=new Stack<TreeNode>();
Stack<TreeNode> s2=new Stack<TreeNode>();
s1.push(left);
s2.push(right);
while(!s1.empty()&&!s2.empty()){
TreeNode left1=s1.pop();
TreeNode right1=s2.pop();
if(left1!=null&&right1!=null){
if(left1.val!=right1.val){
return false;
}else{
if(left1.right!=null){
s1.push(left1.right);
}else{
s1.push(null);
}
if(left1.left!=null){
s1.push(left1.left);
}else{
s1.push(null);
}
if(right1.left!=null){
s2.push(right1.left);
}else{
s2.push(null);
}
if(right1.right!=null){
s2.push(right1.right);
}else{
s2.push(null);
}
}
}else if(left1==null&&right1!=null){
return false;
}else if(left1!=null&&right1==null){
return false;
}else if(left1==null&&right1==null){
}
}
return true;
}
}
