快捷導(dǎo)航

Python二叉樹的鏡像轉(zhuǎn)換實(shí)現(xiàn)方法示例

更新時(shí)間：2019年03月06日 15:06:35 作者：goddaniel

這篇文章主要介紹了Python二叉樹的鏡像轉(zhuǎn)換實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了二叉樹鏡像轉(zhuǎn)換的原理及Python相關(guān)算法實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了Python二叉樹的鏡像轉(zhuǎn)換實(shí)現(xiàn)方法。分享給大家供大家參考，具體如下：

問題描述

操作給定的二叉樹，將其變換為源二叉樹的鏡像。

思路描述

1. 代碼比文字更直觀

2. 文字描述：新建一個(gè)二叉樹，利用遞歸法，將源二叉樹上的左節(jié)點(diǎn)賦值到新二叉樹的右節(jié)點(diǎn)，將源二叉樹上的右節(jié)點(diǎn)賦值到新二叉樹的左節(jié)點(diǎn)。

Python代碼

# 方式1：生成新的鏡像二叉樹
def getMirrorBST(self, root):
  if root == None:
    return
  newTree = treeNode(root.val)
  newTree.right = self.getMirrorBST(root.left)
  newTree.left = self.getMirrorBST(root.right)
  return newTree

但是提交代碼后，說通過率為0… 原來要求將原有的二叉樹就地改成鏡像二叉樹…如此一來，代碼就更簡(jiǎn)單了：因?yàn)榻粨Q根節(jié)點(diǎn)的左右子節(jié)點(diǎn)時(shí)，以左右子節(jié)點(diǎn)為根節(jié)點(diǎn)的左子樹和右子樹也會(huì)交換位置。最終的Python代碼如下：

# 方式2：改變給定的二叉樹為鏡像二叉樹
def turnToMirror(self, root):
  if root == None:
    return
  root.right, root.left = root.left, root.right
  self.turnToMirror(root.left)
  self.turnToMirror(root.right)
  return root

包含測(cè)試代碼的最終代碼如下：

class Solution:
  # 給定一個(gè)二叉樹，獲得其鏡像（軸對(duì)稱）的鏡像二叉樹：
  # 方式1：生成新的鏡像二叉樹
  def getMirrorBST(self, root):
    if root == None:
      return
    newTree = treeNode(root.val)
    newTree.right = self.getMirrorBST(root.left)
    newTree.left = self.getMirrorBST(root.right)
    return newTree
  # 方式2：改變給定的二叉樹為鏡像二叉樹
  def turnToMirror(self, root):
    if root == None:
      return
    root.right, root.left = root.left, root.right
    self.turnToMirror(root.left)
    self.turnToMirror(root.right)
    return root
  # 給定二叉樹的前序遍歷和中序遍歷，獲得該二叉樹
  def getBSTwithPreTin(self, pre, tin):
    if len(pre)==0 | len(tin)==0:
      return None
    root = treeNode(pre[0])
    for order,item in enumerate(tin):
      if root .val == item:
        root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])
        root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])
        return root
class treeNode:
  def __init__(self, x):
    self.left = None
    self.right = None
    self.val = x
if __name__ == '__main__':
  flag = "turnToMirror"
  solution = Solution()
  preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]
  middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]
  treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)
  if flag == "mirrorBST":
    newRoot = solution.getMirrorBST(treeRoot1)
    print(newRoot)
  if flag == "turnToMirror":
    solution.turnToMirror(treeRoot1)
    print(treeRoot1)

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: