剑指Offer28-对称的二叉树

兴趣爱好交流 每日一题
1

剑指Offer28-对称的二叉树

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

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

示例 1：


输入：root = [1,2,2,3,4,4,3]

输出：true

示例 2：


输入：root = [1,2,2,null,3,null,3]

输出：false

限制：


0 <= 节点个数 <= 1000

来源：力扣（LeetCode）

链接：力扣

一解

使用递归，递归条件如下：

  • 判断“左孩子L”和“右孩子R”是否相等

  • 判断“L.left”和“R.right”是否相等

  • 判断“L.right”和“R.left”是否相等


# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def isSymmetric(self, root: TreeNode) -> bool:

        def recur(L, R):

            if not L and not R: return True

            if not L or not R or L.val != R.val: return False

            return recur(L.left, R.right) and recur(L.right, R.left)

        return recur(root.left, root.right) if root else True
2 
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def debug(self):
        def _debug(nodes):
            for i in nodes:
                if i:
                    yield i.val
                else:
                    yield None
            result = []
            for i in nodes:
                if i:
                    result.append(i.left)
                    result.append(i.right)
            for i in result:
                if i:  # 结束递归是所有子节点全部为None
                    yield from _debug(result)
                    break

        return list(_debug([self]))


class Tree:
    def __init__(self, node_values: list):
        nodes = [TreeNode(i) if i else None for i in node_values]
        self.root = nodes[0]
        n = 0
        while 2 * n + 1 < len(nodes):
            nodes[n].left, nodes[n].right = nodes[2 * n + 1], nodes[2 * n + 2]
            n += 1


def is_symmetric(root: TreeNode):
    def recur(l: TreeNode, r: TreeNode):
        if not l and not r: return True  # 递归终止条件
        if not l or not r or l.val != r.val: return False  # 先判断是否有空，有空那么一定不相等，在判断值是否相等
        return recur(l.left, r.right) and recur(l.right, r.left)

    return recur(root.left, root.right)


assert (is_symmetric(Tree([1, 2, 2, 3, 4, 4, 3]).root))
assert not (is_symmetric(Tree([1, 2, 2, None, 3, None, 3]).root))
3

感觉剑指offer的题好难啊