使用Python怎么實現(xiàn)一個對稱的二叉樹

使用Python怎么實現(xiàn)一個對稱的二叉樹？相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

對稱二叉樹的含義非常容易理解，左右子樹關于根節(jié)點對稱，具體來講，對于一顆對稱二叉樹的每一顆子樹，以穿過根節(jié)點的直線為對稱軸，左邊子樹的左節(jié)點=右邊子樹的右節(jié)點，左邊子樹的右節(jié)點=左邊子樹的左節(jié)點。所以對稱二叉樹的定義是針對一棵樹，而判斷的操作是針對節(jié)點，這時可以采取由上到下的順序，從根節(jié)點依次向下判斷，只需要重復調用函數(shù)，不需要回溯。

題目：對稱的二叉樹題：

請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的。注意，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的

解題思路一：先遍歷右子節(jié)點再遍歷左子節(jié)點。注意，我們必須把遍歷二叉樹時遇到的空指針考慮進來。

class Solution:
  def isSymmetrical(self, pRoot):
    # write code here
    return self.isSymmetricalCore(pRoot,pRoot)
  
  def isSymmetricalCore(self,pRoot1,pRoot2):
    if not pRoot1 and not pRoot2:
      return True
    if not pRoot1 or not pRoot2:
      return False
    if pRoot1.val != pRoot2.val:
      return False
    return self.isSymmetricalCore(pRoot1.left,pRoot2.right) and self.isSymmetricalCore(pRoot1.right,pRoot2.left)

解題思路二：迭代

def isSymmetric(self, root: 'TreeNode') -> 'bool':
  stack = root and [(root.left, root.right)]    
  while stack:
    p1, p2 = stack.pop()
    if not p1 and not p2: continue
    if not p1 or not p2: return False
    if p1.val != p2.val: return False
    stack.append((p1.left, p2.right))
    stack.append((p1.right, p2.left))
  return True

看完上述內(nèi)容，你們掌握使用Python怎么實現(xiàn)一個對稱的二叉樹的方法了嗎？如果還想學到更多技能或想了解更多相關內(nèi)容，歡迎關注億速云行業(yè)資訊頻道，感謝各位的閱讀！