剑指Offer[28]-对称的二叉树

题目

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [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

python代码

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def judge(node1,node2):
            if not (node1 and node2):
                if node1 or node2:
                    return False
                else:
                    return True
            if node1.val != node2.val:
                return False
            res1 = judge(node1.left,node2.right)
            res2 = judge(node1.right,node2.left)
            return res1 and res2

        if root:
            return judge(root.left,root.right)
        else:
            return True

这道题的解题思路为递归,解题的关键在于看清这道题的实质—判断A节点的左子节点和B的右子节点的值是否相等。

递归的主体:

        def judge(node1,node2):
            if not (node1 and node2):
                if node1 or node2:
                    return False
                else:
                    return True
            if node1.val != node2.val:
                return False
            res1 = judge(node1.left,node2.right)
            res2 = judge(node1.right,node2.left)
            return res1 and res2

先确定递归的边界:

  • 两个节点均为None
  • 存在一节点为None,一节点不为None
  • 两节点均不为None,但值不相同

循环体:

res1 = judge(node1.left,node2.right)
res2 = judge(node1.right,node2.left)

因为题干是判断对称二叉树,即A的左子节点要与B的右子节点相同,A的右子节点与B的左子节点相同。

发表评论

电子邮件地址不会被公开。