파이썬 트리와 트리의 거울

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

좋은 웹페이지 즐겨찾기