파이썬 트리와 트리의 거울
7695 단어 python 검지 offer
1. 제목 설명
주어진 두 갈래 트리를 조작하여 원본 두 갈래 트리의 거울로 변환합니다.
2. 설명 입력
:
8
/ \
6 10
/ \ / \
5 7 9 11
8
/ \
10 6
/ \ / \
11 9 7 5
3. 생각
이전에 이 나무의 모든 결점을 두루 훑어보았는데, 만약 두루 훑어본 결점에 자결점이 있다면, 그 두 개의 자노드를 교환하고, 모든 비엽결점의 좌우 자결점을 교환한 후에 나무의 거울을 얻게 된다.
이 프로그램은 다음 두 갈래 트리의 대칭복사를 실현합니다.
:
E
/ \
A G
\ \
C F
/ \
B D
:
E
/ \
G A
/ /
F C
/ \
D B
4. Python 프로그램 코드는 다음과 같습니다.
# -*- coding: utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# ,
def preTravese(root):
if root is None:
return 0
print(root.val, end=' ')
preTravese(root.left)
preTravese(root.right)
#
class Solution:
def mirror(self, root):
if root is None:
return 0
if root is not None:
root.left, root.right = root.right, root.left #
self.mirror(root.left)
self.mirror(root.right)
return root
if __name__ == '__main__':
#
a = TreeNode("A")
b = TreeNode("B")
c = TreeNode("C")
d = TreeNode("D")
e = TreeNode("E")
f = TreeNode("F")
g = TreeNode("G")
#
e.left = a
e.right = g
a.right = c
c.left = b
c.right = d
g.right = f
#
root = e
print(" :")
preTravese(root)
s = Solution()
print("
")
print(" :")
preTravese(s.mirror(root))
실행 결과:
:
E A C B D G F
:
E G F A C D B
Process finished with exit code 0