当前位置: 萬仟网 > IT编程>数据库>Redis > 剑指Offer 28. 对称的二叉树

剑指Offer 28. 对称的二叉树

2020年11月19日  | 萬仟网IT编程  | 我要评论
剑指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

如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!

相关文章:

验证码:
Copyright © 2017-2020  萬仟网 保留所有权利. 粤ICP备17035492号-1