0101：对称二叉树

2015-04-11 约 270 字预计阅读 1 分钟次阅读

力扣第 101 题

题目

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

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

示例 2：

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

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

分析

#1

0100 升级版，等价于判断左子树和右子树是否镜像对称
令 dfs(p, q) 代表 p 和 q 是否镜像对称，即可递归

1
2
3
4
5
6
7


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(p,q):
            if not p or not q:
                return not p and not q
            return p.val==q.val and dfs(p.left,q.right) and dfs(p.right,q.left)
        return dfs(root.left,root.right)

42 ms

#2

也可以用栈遍历迭代，改下入栈顺序即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        sk = [(root.left,root.right)]
        while sk:
            a,b = sk.pop()
            if not a and not b:
                continue
            if not a or not b or a.val!=b.val:
                return False
            sk.extend([(a.left,b.right),(a.right,b.left)])
        return True

32 ms

目录

0101：对称二叉树

题目

分析

#1

#2

解答