LeetCode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

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

---

For the recursive way, we can do the check by following the definition. Recursively check the value of left child with right child, left child's left child with right child's right child, and left child's right child with right child's left child. For the iterative way, we can traverse the tree in level order and test if each level is symmetric.

C++ Code:

/*
 * func: symmetric_tree_helper
 * goal: helper function for checking tree symmetric
 * @param left: left subtree
 * @param right: right subtree
 * return: tree or false
 */
bool symmetric_tree_helper(TreeNode *left, TreeNode *right){
    if(!left && !right){
        return true;
    }else if(left && right){
        return left->val == right->val && symmetric_tree_helper(left->left, right->right)
        && symmetric_tree_helper(left->right, right->left);
    }else{
        return false;
    }
}
/*
 * func: symmetric_tree
 * goal: to check if the input tree is symmetric
 * @param root: root node of the tree
 * return: True or False
 */
bool symmetric_tree(TreeNode *root){
    return (!root || symmetric_tree_helper(root->left, root->right));
}

Python Code:

# func: to chec if current level is symmetric
# @param level: current level of the tree
# @return: True or False
def check_symmetric(level):
    if len(level) <= 1:
        return True
    elif len(level) & 1 == 0:
        mid = len(level)/2
        for i in xrange(0, mid):
            if level[i] is None and level[-(i+1)] is None:
                continue
            elif level[i] is not None and level[-(i+1)] is not None and level[i].val == level[-(i+1)].val:
                continue
            else:
                return False
        return True
    else:
        return False

# func: to check if the tree is symmetric
# @param root: root node of the tree
# @return: True or False
def is_symmetric(root):
    if not root:
        return True
    else:
        level = [root]
        while level:
            if check_symmetric(level):
                tmp_queue = []
                for node in level:
                    if node:
                        tmp_queue.append(node.left)
                        tmp_queue.append(node.right)
                level = tmp_queue[:]
            else:
                return False
        return True