溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

如何分析python中的對稱二叉樹

發(fā)布時(shí)間:2021-12-13 15:14:04 來源:億速云 閱讀:106 作者:柒染 欄目:大數(shù)據(jù)

如何分析python中的對稱二叉樹,針對這個(gè)問題,這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

對稱二叉樹

 

題目

給定一個(gè)二叉樹,檢查它是否是鏡像對稱的。

例如,二叉樹 [1,2,2,3,4,4,3] 是對稱的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對稱的:

    1
   / \
  2   2
   \   \
   3    3
 

來源:力扣(LeetCode)鏈接:https://leetcode-cn.com/problems/symmetric-tree/submissions/

# 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
        """
   

錯(cuò)誤代碼

判斷二叉樹是否對稱,先看看下面代碼是否正確,它實(shí)現(xiàn)的什么功能?

首先看遞歸基,分三種情況:

  1. 沒有根,就是空樹,返回True
  2. 沒有左右子樹,返回True
  3. 左右子節(jié)點(diǎn)     val不相等,返回False

遞歸方程如下,判斷左、右子樹都對稱。

self.isSymmetric(root.left) and self.isSymmetric(root.right)
 
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True 
        if not root.left and not root.right:
            return True 
        return root.left == root.right and self.isSymmetric(root.left) and self.isSymmetric(root.right)
 

以上代碼認(rèn)為下面的二叉樹才是對稱的:

如何分析python中的對稱二叉樹  

這與題目要求的對稱二叉樹明顯不同,這樣才是真的對稱二叉樹:

如何分析python中的對稱二叉樹  
 

正確代碼

錯(cuò)誤代碼錯(cuò)誤的原因在于遞歸方程有問題。請看下圖:

如何分析python中的對稱二叉樹  

因此,得到正確的遞歸方程:

sub(left.left,right.right) and sub(left.right,right.left)
 

完整代碼:

class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True 
        def sub(left,right):
            # 沒有左和右,返回True
            if not left and not right:
                return True
            # 沒有左或沒有右,返回False
            if not left or not right:
                return False
            return left.val == right.val and sub(left.left,right.right) and sub(left.right,right.left)
        return sub(root.left,root.right)

關(guān)于如何分析python中的對稱二叉樹問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。

向AI問一下細(xì)節(jié)

免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI