Python의 주어진 트리에서 가장 큰 이진 검색 하위 트리를 찾는 프로그램

이진 트리가 있다고 가정하면 이진 검색 트리로 가장 큰 하위 트리(최대 노드 수)를 찾아야 합니다.

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

그러면 출력은

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

• 최대 크기 :=[0]
• max_node :=[null]
• traverse() 함수를 정의합니다. 노드가 필요합니다.
• 노드가 null이면
  • null 반환
• left :=traverse(노드의 왼쪽)
• right :=traverse(노드 오른쪽)
• lst :=왼쪽 + [노드 값] + 오른쪽
• lst가 정렬되면
  • max_size[0]
  • max_size[0] :=lst의 크기
  • max_node[0] :=노드

예제(파이썬)

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)
class Solution:
   def solve(self, root):
      max_size = [0]
      max_node = [None]
      def traverse(node):
         if not node:
            return []
      left = traverse(node.left)
      right = traverse(node.right)
      lst = left + [node.val] + right
      if sorted(lst) == lst:
         if max_size[0] < len(lst):
            max_size[0] = len(lst)
            max_node[0] = node
      return lst

   traverse(root)
   return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

입력

root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)

출력

4, 5, 6,