LeetCode #101 Symmetric Tree

Easy

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 — Recursion

Recursively check left subtree and right subtree by switching their root node.

Complexity

Because we will traverse entire left subtree and right subtree of root node, it costs O(n/2) = O(n) time. The calling stack may also be the same, which means it needs O(n) extra space.

Solution — Iteration

Use a deque to save each level information and compare node in each ends.

Complexity

It needs to compare every nodes of left subtree and right subtree of root node, so the time complexity is O(n/2) = O(n). And the deque should have ability to save all leaves of this tree, which means it needs O(n) extra space.