DEV Community

Masaki Fukunishi
Masaki Fukunishi

Posted on

LeetCode #101 Symmetric Tree with JavaScript

Solutions to LeetCode's 101. Symmetric Tree with JavaScript.

Follow up: Could you solve it both recursively and iteratively?

Solution 1: Recursive

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric1 = (root) => {
  const isMirror = (left, right) => {
    if (!left && !right) return true;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
  };
  return isMirror(root, root);
};
Enter fullscreen mode Exit fullscreen mode
  • Time complexity: O(n)
  • Space complexity: O(n)

Solution 2: Iterative BFS

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric2 = (root) => {
  const queue1 = [root.left];
  const queue2 = [root.right];

  while (queue1.length > 0 || queue2.length > 0) {
    const dequeued1 = queue1.shift();
    const dequeued2 = queue2.shift();

    if (!dequeued1 && !dequeued2) continue;
    if (!dequeued1 || !dequeued2) return false;
    if (dequeued1.val !== dequeued2.val) return false;

    queue1.push(dequeued1.left);
    queue1.push(dequeued1.right);
    queue2.push(dequeued2.right);
    queue2.push(dequeued2.left);
  }
  return true;
};
Enter fullscreen mode Exit fullscreen mode
  • Time complexity: O(n)
  • Space complexity: O(n)

I used BFS to solve the problem with iteration.

Top comments (0)