Leetcode 101：对称二叉树（超详细的解法！！！）

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

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

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

解题思路

这个问题非常简单。我们首先要判断root是不是空，如果是的话，我们直接返回True即可。否则的话，我们要进行如下几种判断

• left == None and right == None
• left == None or right == None
• left.val != right.val

如果是第一种的话，我们直接返回True。对于第二种和第三种的话，我们返回False。接着就是left.val == right.val，此时我们只需要递归下去，判断left.left and right.right和left.right and right.left是不是同样成立即可。

class Solution:
    def isSymmetric(self, root):
        \"\"\"
        :type root: TreeNode
        :rtype: bool
        \"\"\"
        if not root:
            return True
        
        return self.helper(root.left, root.right)
        
    def helper(self, left, right):
        if left == None and right == None:
            return True
        elif left == None or right == None:
            return False
        elif left.val != right.val:
            return False
        else:
            return self.helper(left.left, right.right) and self.helper(left.right, right.left)    

我们同样可以通过递归解决这个问题，只要建立一个栈，每次将left.left,right.right,left.right,right.left依次入栈即可。

class Solution:
    def isSymmetric(self, root):
        \"\"\"
        :type root: TreeNode
        :rtype: bool
        \"\"\"
        if not root:
            return True
        
        stack = list()
        stack.append(root.left)
        stack.append(root.right)
        while stack:
            right = stack.pop()
            left = stack.pop()
            if left == None and right == None:
                continue
                
            if (left == None or right == None) or (left.val != right.val):
                return False
            
            stack.append(left.left)
            stack.append(right.right)
            stack.append(left.right)
            stack.append(right.left)
            
        return True

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！