資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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。
- 返回結果。
示例
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”，因此它是一個高度平衡樹。
更新於：2021年2月23日
4K+ 瀏覽量
廣告