content: package question0101_symmetric_tree;
  
  import java.util.LinkedList;
  import java.util.Queue;
  
  /**
   * 迭代实现。
   *
   * 时间复杂度是O(n)，其中n为二叉树中的节点个数。空间复杂度是O(h)，其中h是二叉树的高度。
   *
   * 执行用时：3ms，击败28.99%。消耗内存：35.9MB，击败79.48%。
   */
  public class Solution2 {
      public boolean isSymmetric(TreeNode root) {
          if (root == null) {
              return true;
          }
          Queue<TreeNode> queue = new LinkedList<>();
          queue.add(root);
          queue.add(root);
          while (!queue.isEmpty()) {
              TreeNode node1 = queue.poll(), node2 = queue.poll();
              if (node1 == null && node2 == null) {
                  continue;
              }
              if (node1 == null || node2 == null) {
                  return false;
              }
              if (node1.val != node2.val) {
                  return false;
              }
              queue.add(node1.left);
              queue.add(node2.right);
              queue.add(node1.right);
              queue.add(node2.left);
          }
          return true;
      }
  }