101. Symmetric Tree

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.

// Recursion
bool isSymmetric(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return true;
    return helper(root->left, root->right);
}
bool helper(TreeNode* left, TreeNode* right) {
    if (!left || !right) return left == right;
    if (left->val != right->val) return false;
    return helper(left->left, right->right) && helper(left->right, right->left);
}

// Level Order Traversal Iteration
bool isSymmetric(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return true;
    queue<TreeNode*> q1, q2;
    TreeNode* left = root->left, *right = root->right;
    q1.push(left);
    q2.push(right);
    while (!q1.empty() && !q2.empty()) {
        left = q1.front(); q1.pop();
        right = q2.front(); q2.pop();
        if (!left && !right) continue;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        q1.push(left->left);
        q1.push(left->right);
        q2.push(right->right);
        q2.push(right->left);
    }
    return true;
}