平衡二叉樹的定義:
它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1卜壕，并且左右兩個子樹都是一棵平衡二叉樹，同時，平衡二叉樹必定是二叉搜索樹糊昙，反之則不一定.
問題1:
把一個升序的數(shù)組轉換成平衡二叉樹
對一個二叉搜索樹進行中序遍歷就可以得到一個升序的數(shù)組,那么反過來考慮,數(shù)組的中值即為root,然后數(shù)組分為左子樹和右子樹,繼續(xù)進行遞歸即可得出結果.
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
問題2:
給一個二叉樹,判斷是否是平衡樹
首先寫計算二叉樹高度的函數(shù)
樹的高度 = max(左子樹高度，右子樹高度)+1
def getHeight(self, root):
if not root:
return 0
return 1 + max(self.getHeight(root.left), self.getHeight(root.right))
可以得到高度后對樹遞歸求解每個節(jié)點的左右子樹的高度差谢谦，如果有大于1的释牺，則return False
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)
