Python의 균형 이진 트리

이진 트리에서 각 노드는 두 개의 자식, 즉 왼쪽 자식과 오른쪽 자식을 포함합니다. 이진 트리가 있고 트리가 균형을 이루고 있는지 확인해야 한다고 가정해 보겠습니다. 이진 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 '1'보다 작거나 같으면 균형이 맞춰졌다고 합니다.

예

입력-1:

<강한>

출력:

True

설명:

주어진 이진 트리는 [1,2,3, NULL, NULL, 6, 7]입니다. 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 '1'이므로 높이 균형 트리입니다.

입력-2:

<강한>

출력:

False

설명:

주어진 이진 트리는 [1,2,3,4, NULL, NULL, NULL,5]입니다. 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크므로 높이 균형 트리가 아닙니다.

이 문제를 해결하기 위한 접근 방식

이 문제를 해결하기 위한 재귀적 접근 방식은 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 찾은 다음 (height(leftsubstree) - height(rightsubtree) <=1)인지 확인하고 그에 따라 True 또는 False를 반환하는 것입니다. 그런 다음 이진 트리의 각 노드에 대해 재귀적으로 확인합니다.

• 이진 트리의 노드를 입력합니다.
• 나무의 높이를 찾는 함수를 정의합니다.
• 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 '1' 이하인지 재귀적으로 확인하고 True를 반환하는 Boolean 함수입니다.
• 결과를 반환합니다.

예시

class treenode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
# funtion to find the height of the left subtree and right subtree
class height:
   def __init__(self):
      self.height = 0
# function to check if the tree is balanced or not
def isBalanced(root):
   lh = height()
   rh = height()
   if root is None:
      return True
   return (
      (abs(lh.height - rh.height) <= 1)
      and isBalanced(root.left)
      and isBalanced(root.right)
   )
root = treenode(1)
root.left = treenode(2)
root.right = treenode(3)
root.left.left = None
root.left.right = None
root.right.left = treenode(6)
root.right.right = treenode(7)
if isBalanced(root):
   print("Balanced")
else:
   print("Not Balanced")

위의 코드를 실행하면 출력이 다음과 같이 생성됩니다.

출력

Balanced

주어진 이진 트리 [1, 2, 3, NULL, NULL, 6, 7]. 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 '1'이므로 높이 균형 트리입니다.