剑指Offer. 对称的二叉树
程序员文章站
2022-03-22 14:34:40
剑指Offer 28. 对称的二叉树1. 题目描述请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。例如,二叉树 [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 32. 解题思路对称二叉树的判断,首先要清楚比较的位置:对...
剑指Offer 28. 对称的二叉树
1. 题目描述
请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。
例如,二叉树 [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
2. 解题思路
对称二叉树的判断,首先要清楚比较的位置:对称位置的节点的值进行比较。
- 如果对称位置处的节点的值相等,则递归比较其他对称位置,对称,则返回True,否则返回False;
- 如果树为空或者为空树,则返回True;
- 如果某个对称位置处的节点为null,则这棵二叉树一定不是对称二叉树;
3.python代码实现
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def recur(L, R):
# 如果对称位置均为空,则返回True
if not L and not R: return True
# 如果对称位置有一个为空一个不为空 或者 均不为空但是值不相等,则返回False
if not L or not R or L.val != R.val: return False
# 递归对称位置
result = recur(L.left, R.right) and recur(L.right, R.left)
return result
# 如果为空树,返回True;否则调用函数recur(),传入根节点的左右节点
return recur(root.left, root.right) if root else True
4. 知识点
- 对称二叉树的判断,即判断对称位置的节点是否相等
- 递归思想
本文地址:https://blog.csdn.net/qq_40576653/article/details/109828931
推荐阅读
-
《剑指offer》面试题6 重建二叉树
-
剑指offer25:复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),结果返回复制后复杂链表的head。
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
[算法练习-剑指offer]题18.二叉树的镜像(Java)