?

递归方案：

?

bool isSymmetric(TreeNode *root) {
        if (!root) return true;
        return helper(root->left, root->right);
    }

    bool helper(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        } else if (!p || !q) {
            return false;
        }

        if (p->val != q->val) {
            return false;
        }

        return helper(p->left,q->right) && helper(p->right, q->left); 
    }

?

?

python版本：

?

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def helper(self, a, b):
        if a is None and b is None:
            return True
        if a is None and b is not None:
            return False
        if a is not None and b is None:
            return False
        if a.val != b.val: 
            return False
        return self.helper(a.left, b.right) and self.helper(a.right,b.left)
    def isSymmetric(self, root):
        if root is None:
            return True
        return self.helper(root.left, root.right)

?

?

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isSymmetric(self, root):
        # no tree
        # is identical
        if root is None: return True
        if not self.is_identical(root.left, root.right): return False

        queue = []
        # root is identical
        # proceed to queue up the next level
        # (node, depth)

        if root.left:
            enqueue(queue, (root.left, 1))

        if root.right:
            enqueue(queue, (root.right, 1))

        while queue:

            same_level = True
            level = []
            while same_level:
                # still the same level
                if len(queue) > 0 and (len(level) == 0 or level[-1][1] == queue[0][1]):
                    child = dequeue(queue)
                    level.append(child)
                    # enqueue children now to maintain level order
                    # add to the depth
                    if child[0].left:
                        enqueue(queue, (child[0].left, child[1]+1))
                    if child[0].right:
                        enqueue(queue, (child[0].right, child[1]+1))   
                else:
                    same_level = False

            # symmetrical has to be even
            if len(level) % 2 != 0: return False
            while level:
                # grab the two extreme ends 
                (left_node, _), (right_node, _) = level.pop(0), level.pop()
                if not self.is_identical(left_node, right_node): return False


        return True

    def is_identical(self, left, right):
        # if any of them is none, they need to be both none
        if left is None or right is None:
            return left == right

        # their value should equal
        if left.val != right.val:
            return False

        # if left has a left, then right needs to have right
        if left.left:
            if right.right is None:
                return False


        # if left has a right, then right needs to have left
        if left.right:
            if right.left is None:
                return False

        return True




def enqueue(queue, item):
    queue.append(item)

def dequeue(queue):
    return queue.pop(0)

?

?