LeetCode 101 [Symmetric Tree]

原题

给定一个二叉树，检查他是不是自己的镜像(轴对称)

样例

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

是对称二叉树

    1
   / \
  2   2
   \   \
   3    3

不是对称二叉树

解题思路

• 写一个helper函数，递归求解，但注意helper函数的形参left和right不是指的左儿子和右儿子。那上面的例子为例，我们要传入3，3和4，4
• Divide and Conquer的思路 - 如果left.left, right.right和left.right, right.left都对称则整棵树对称

完整代码

# 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 root:
            return self.helper(root.left, root.right)
        return True
            
    def helper(self, left, right):
        if left is None and right is None:
            return True
        if left and right and left.val == right.val:
            return self.helper(left.left, right.right) and \
                    self.helper(left.right, right.left)
        return False