判断是否为镜像树

对于树中的任意两个对称节点L、R，必然有：

• L 和 R 节点的值相等；
• L 的左节点和 R 的右节点对称
• L 的右节点和 R 的左节点对称
  所以知道对称二叉树的定义后，可以看出来对称二叉树的定义是递归的，所以考虑从顶部节点开始往下递归，判断递归的每队节点是否对称，只要有一对节点不对称，那么整颗树就不是对称，反之，如果每对节点都对称，那么整棵树是对称。
  主要包括两种实现方式，递归和非递归。下面直接展示对应的实现代码，具体分析思路可以参考引用链接。

递归版实现：

 public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        //从两个子节点开始判断
        return recur(root.left, root.right);
    }

    public boolean recur(TreeNode left, TreeNode right) {
        //如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if (left == null && right == null)
            return true;
        //如果当前节点只有一个子节点或者有两个子节点，但两个子节点的值不相同，直接返回false
        if (left == null || right == null || left.val != right.val)
            return false;
        //然后左子节点的左子节点和右子节点的右子节点比较，左子节点的右子节点和右子节点的左子节点比较
        return recur(left.left, right.right) && recur(left.right, right.left);
    }

非递归实现：

public boolean isSymmetric(TreeNode root) {
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null)
        return true;
    //左子节点和右子节点同时入队
    queue.add(root.left);
    queue.add(root.right);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //每两个出队
        TreeNode left = queue.poll(), right = queue.poll();
        //如果都为空继续循环
        if (left == null && right == null)
            continue;
        //如果一个为空一个不为空，说明不是对称的，直接返回false
        if (left == null ^ right == null)
            return false;
        //如果这两个值不相同，也不是对称的，直接返回false
        if (left.val != right.val)
            return false;
        //这里要记住入队的顺序，他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队，因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队，
        //因为他俩会同时比较
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}

引用链接：https://mp.weixin.qq.com/s/GoazAB2M6PobOzPInch-KA