Cho mảng đã sắp xếp A. Tạo cây BST cân bằng chiều cao (độ sâu hai cây con chênh lệch ≤1). Ví dụ: [-10,-3,0,5,9] → [0,-3,9,-10,null,5].
Giải pháp
Đệ quy:
- Nếu A rỗng → Null.
- Chọn phần tử giữa làm gốc.
- Chia mảng thành hai phần trái/phải, đệ quy xây cây con.
Ví dụ
Triển khai Python:
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
# ... (hàm hỗ trợ insert, in cây)
class Solution(object):
def sortedArrayToBST(self, nums):
if not nums:
return None
mid = nums[len(nums)//2]
root = TreeNode(mid)
root.left = self.sortedArrayToBST(nums[:len(nums)//2])
root.right = self.sortedArrayToBST(nums[len(nums)//2 +1 :])
return root
nums = [-10,-3,0,5,9]
ob1 = Solution()
bst = ob1.sortedArrayToBST(nums)
level_order(bst) Đầu vào
nums = [-10,-3,0,5,9]
Đầu ra
[0,-3,9,-10,5,]