ในไบนารีทรี แต่ละโหนดมีลูกสองคน นั่นคือลูกด้านซ้ายและลูกด้านขวา สมมติว่าเรามีไบนารีทรีและเราต้องตรวจสอบว่าต้นไม้นั้นสมดุลหรือไม่ ต้นไม้ไบนารีกล่าวกันว่ามีความสมดุลหากความแตกต่างของความสูงของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวามีค่าน้อยกว่าหรือเท่ากับ '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
- ส่งคืนผลลัพธ์
ตัวอย่าง
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' ดังนั้นจึงเป็นต้นไม้ที่มีความสูงสมดุล
