Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

    For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1.         1
    2.    / \
    3.   2   2
    4.  / \ / \
    5. 3  4 4  3

    But the following [1,2,2,null,3,null,3] is not:

    1.         1
    2.    / \
    3.   2   2
    4.    \   \
    5.    3    3

    Note:
    Bonus points if you could solve it both recursively and iteratively.

    题意

    判断一个树是否关于中心轴对称。

    思路

    递归或利用队列迭代来判断。

    代码实现 - 迭代

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public boolean isSymmetric(TreeNode root) {
    12.         if (root == null) {
    13.             return true;
    14.         }
    15.         // 如果以两个root作为递归起点则会导致接下来的每个点都被访问2次
    16.         return isSymmetric(root.left, root.right);
    17.     }
    19.     private boolean isSymmetric(TreeNode x, TreeNode y) {
    20.         if (x == null && y == null) {
    21.             return true;
    22.         } else if (x == null || y == null || x.val != y.val) {
    23.             return false;
    24.         } else {
    25.             return isSymmetric(x.left, y.right) && isSymmetric(x.right, y.left);
    26.         }
    27.     }
    28. }

    代码实现 - 迭代

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public boolean isSymmetric(TreeNode root) {
    12.         if (root == null) {
    13.             return true;
    14.         }
    15.         // 注意不能使用ArrayDeque，因为ArrayDeque不能插入null
    16.         Queue<TreeNode> q = new LinkedList<>();
    17.         // 如果插入两个root则会导致接下来的每个点都入队了2次
    18.         q.offer(root.left);
    19.         q.offer(root.right);
    20.         while (!q.isEmpty()) {
    21.             TreeNode x = q.poll();
    22.             TreeNode y = q.poll();
    23.             if (x == null && y == null) {
    24.                 continue;
    25.             } else if (x == null || y == null || x.val != y.val) {
    26.                 return false;
    27.             } else {
    28.                 q.offer(x.left);
    29.                 q.offer(y.right);
    30.                 q.offer(x.right);
    31.                 q.offer(y.left);
    32.             }
    33.         }
    34.         return true;
    35.     }
    36. }