101. Symmetric Tree

Problem:

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
   / \
  2   2
 / \ / \
3  4 4  3

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

1
   / \
  2   2
   \   \
   3    3

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

Solution:

ONE

The result of pre-order and post-order traversal on a symmetric tree should be the same.

So just like 100. Same Tree. Except one is pre-order traversal and the other is post-order.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
let isSymmetric = function (root) {
  return root === null || isSymmetricTree(root.left, root.right);
};

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
function isSymmetricTree(p, q) {
  return (
    (p === null && q === null) ||
    (p !== null &&
      q !== null &&
      p.val === q.val &&
      isSymmetricTree(p.left, q.right) &&
      isSymmetricTree(p.right, q.left))
  );
}

TWO

Level order traversal. Check symmetry before entering the next level.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
let isSymmetric = function (root) {
  if (root === null) {
    return true;
  }

  const queue = [NaN, root];

  while (queue.length > 1) {
    const node = queue.shift();
    if (node !== node) {
      for (let i = 0, j = queue.length - 1; i <= j; i++, j--) {
        if (
          (queue[i] === null && queue[j] !== null) ||
          (queue[i] !== null && queue[j] === null) ||
          (queue[i] !== null &&
            queue[j] !== null &&
            queue[i].val !== queue[j].val)
        ) {
          return false;
        }
      }
      queue.push(NaN);
    } else {
      if (node !== null) {
        queue.push(node.left);
        queue.push(node.right);
      }
    }
  }

  return true;
};

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆