递归

1. 分析

不对称的条件：结点X的左右子树不对称，包括左右子树某一个为null，左右孩子的val不同，左孩子的左子树与右孩子的右子树不对称等等
递归的base case是假设知道左右两个子树是否为null、根以及左右子树是否对称。

2. 代码

public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null){
            return true;
        }
        return check(pRoot.left, pRoot.right);
    }
    public boolean check(TreeNode left, TreeNode right){
        if(left== null && right == null){
            return true;
        }else if((left == null || right == null) || (left.val != right.val)){
            return false;
        }
        return check(left.left, right.right)&&check(left.right, right.left);

    }
}

3. 复杂度

时间：O(n)
空间：O(n)

非递归

2.1 分析

广度优先遍历，辅助队列，对称的节点成对入队和出队，出队判断是否对称。深度优先的方法同理，只需要修改出栈时接收的顺序。

2.2 代码

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if(pRoot == null || (pRoot.left == null && pRoot.right == null)){
            return true; 
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot.left);
        q.offer(pRoot.right);
        TreeNode left = null;
        TreeNode right = null;
        while(!q.isEmpty()){
            left = q.poll();
            right = q.poll();
            if(left==null && right == null){
                continue;
            }else if(left==null || right == null){
                return false;
            }
            if(left.val != right.val){
                return false;
            }
            q.offer(left.left);
            q.offer(right.right);
            q.offer(left.right);
            q.offer(right.left);
        }
        return true;
    }
}

2.3 复杂度

时间：O(n)
空间：O(n)