101. 对称二叉树

题目：给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3

进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

解法1：递归，时间复杂度o(n)，空间复杂度o(n)

• 递归结束条件：left和right都为null返回true，left和right只有一个为null返回false

• 对称条件：传入参数left和right，判断对称

  • left.val == right.val
  • left.left.val == right.right.val

  • left.right.val == right.left.val

    class Solution {
    public boolean isSymmetric(TreeNode root) {
       if(root == null)
           return true;
       return help(root.left,root.right);
    }
    public boolean help(TreeNode left,TreeNode right){
       // 如果都为null则是true
       if(left == null && right == null)
           return true;
       // 仅其中一个为null为false
       if(left == null || right == null)
           return false;
       // 当前层的左右值相等，则判断其左右子树
       if(left.val == right.val){
           return  help(left.right,right.left) && help(left.left,right.right) ;
       }else
           return false;
    }
    }

    解法2：非递归，时间复杂度o(n)，空间复杂度o(n)

• 使用一个队列存放当前的根节点的左右节点，

• 两层循环，大循环为每层遍历，小循环为该层的每个节点遍历，每次小循环取出两个节点计算
• 判断规则：
  • left和right都为null 则继续下一次循环
  • left和right仅一个为null，则返回false
  • left和right值相同，则依次添加left.left ,right.right和left.right、right.left
  • left和right值不同，返回false
• 若循环正常结束或没有进入循环则返回true

  import java.util.*;
  class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        Deque<TreeNode> deque = new LinkedList<>();
        // 添加当前左右节点
        deque.add(root.left);
        deque.add(root.right);
        while(!deque.isEmpty()){
            int sz = deque.size();
            for(int i = 0 ; i < sz ; i++){
                // 左右节点出队
                TreeNode left = deque.poll();
                TreeNode right = deque.poll();
                // 判断如果都是null，下一次循环
                if(left == null && right == null)
                    continue;
                // 如果一个为null一个不为null，返回false
                if(left == null || right == null)
                    return false;
                // 如果left和right值相同
                if(left.val == right.val){
                    // 继续观察他们的左右子树
                    deque.add(left.left);
                    deque.add(right.right);
                    deque.add(left.right);
                    deque.add(right.left);
                }else{
                    return false;
                }
            }
        }
        return true;
    }
  }