Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 이진 트리를 반전시키는 프로그램

<시간/>

이진 트리 루트가 있다고 가정하고 왼쪽 하위 트리와 오른쪽 하위 트리가 교환되고 하위 트리도 재귀적으로 교환되도록 반전해야 합니다.

따라서 입력이 다음과 같으면

Python에서 이진 트리를 반전시키는 프로그램

그러면 출력은

Python에서 이진 트리를 반전시키는 프로그램

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • solve() 메서드를 정의하면 노드가 필요합니다.

  • 루트가 null이면

    • 반환

  • 루트 왼쪽 :=해결(루트 오른쪽)

  • 루트 오른쪽 :=해결(루트 오른쪽)

  • 루트 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None

def inorder(root):
   if root:
      inorder(root.left)
      print(root.val, end=', ')
      inorder(root.right)

class Solution:
   def solve(self, root):
   if not root:
      return
   root.left, root.right = self.solve(root.right), self.solve(root.left)
   return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
inv = ob.solve(root)
inorder(inv)

입력

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

출력

15, 10, 7, 5, 4,