对称二叉树

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [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

递归解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return valid(root.left,root.right);
    }

    private boolean valid(TreeNode left,TreeNode right){
        if (left == null && right == null)
            return true;
        if (left != null && right != null && left.val == right.val){
            TreeNode lLeft = left.left;
            TreeNode lRight = left.right;
            TreeNode rLeft = right.left;
            TreeNode rRight = right.right;
            if(!valid(lLeft,rRight))
                return false;
            return valid(lRight,rLeft);
        }
        return false;
    }
}

迭代解法：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        Queue<TreeNode> leftQue = new LinkedList<>();
        Queue<TreeNode> rightQue = new LinkedList<>();
        leftQue.add(root.left);
        rightQue.add(root.right);
        while(!leftQue.isEmpty() && !rightQue.isEmpty()){
            TreeNode left = leftQue.poll();
            TreeNode right = rightQue.poll();
            if (left == null && right == null)
                continue;
            if (right == null || left == null)
                return false;
            //left和right都不为null
            if (left.val != right.val){
                return false;
            }
            leftQue.add(left.left);
            leftQue.add(left.right);
            rightQue.add(right.right);
            rightQue.add(right.left);
        }
        return leftQue.isEmpty() && rightQue.isEmpty();
    }
}