PU Symmetric Tree

    1
   / 
  2   2
 /  / 
3  4 4  3

    1
   / 
  2   2
      
   3    3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool helper(struct TreeNode *l, struct TreeNode *r) {
    if (!l && !r) return true;
    if (!l ^ !r) return false;
    if (l->val != r->val) return false;
    return helper(l->left, r->right) && helper(l->right, r->left);
}
bool isSymmetric(struct TreeNode* root) {
    if (!root) return true;
    return helper(root->left, root->right);
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True
        first = [root]
        second = []
        while first:
            l, r = 0, len(first) - 1
            while l < r:
                if first[l] and not first[r] or not first[l] and first[r]: return False
                if first[l] and first[r] and first[l].val != first[r].val: return False
                l += 1
                r -= 1
            if l < r: return False
            for n in first:
                if not n: continue
                second.append(n.left)
                second.append(n.right)
            first = second
            second = []
        return True