LeetCode 101. 对称二叉树 (Symmetric Tree)[简单]

lework · 2020年03月31日 · 最后由 lework 回复于 2020年03月31日 · 117 次阅读

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

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

说明:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

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

class Solution:
    def childTreeIsSymmetric(self, p, q):
        # 递归结束条件:
        # 1. 两个节点都为空
        # 2. 一个为空,另一个非空
        # 3. 都为非空,但是值不相等
        # 4. 都为非空,但是值相等(再次进入递归)
        if not p or not q:
            # 条件12
            return p == q
            # 条件1返回True,条件2返回False
        if p.val != q.val:
            return False
            # 条件3
        # 条件4
        return self.childTreeIsSymmetric(p.left, q.right) & self.childTreeIsSymmetric(p.right, q.left)

    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        else:
            return self.childTreeIsSymmetric(root.left, root.right)
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册