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
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
解答
思路
两棵对称的树:
- 根节点相同
- 左子树和右子树对称
- 右子树和左子树对称
代码
Python 代码
python
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None or q is None:
return p is q
return p.val == q.val \
and self.isSameTree(p.left, q.right) \
and self.isSameTree(p.right, q.left)
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
return self.isSameTree(root.left, root.right)
这里利用的上一题的代码,其中 isSameTree(p, q)
的含义是 p, q
是否对称。因此只需要 root.left, root.right
对称即可。
TODO:迭代算法