原題
給定一個(gè)二叉樹,確定它是高度平衡的舍肠。對(duì)于這個(gè)問題,一棵高度平衡的二叉樹的定義是：一棵二叉樹中每個(gè)節(jié)點(diǎn)的兩個(gè)子樹的深度相差不會(huì)超過1届氢。
給出二叉樹 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3
/ \ \
9 20 20
/ \ / \
15 7 15 7
二叉樹A是高度平衡的二叉樹彤守，但是B不是
解題思路
- 一般BST的問題挺智，首先往divide & conquer的思路去想
- 一棵二叉樹是不是平衡二叉樹 => 左子樹是不是平衡二叉樹饰迹？右子樹是不是平衡二叉樹商架？
- 如果任意一顆子樹不平衡与纽，整個(gè)樹肯定不平衡
- 如果左右子樹都是平衡的侣签，但左右子樹相差高度大于1，此刻這課樹又是不平衡的
- 問題轉(zhuǎn)化為分別對(duì)左右子樹求maxDepth急迂，平衡就返回最大深度影所，不平衡就返回-1
- 技巧：用-1表示它不是一顆平衡二叉樹
完整代碼
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.maxDepth(root) != -1
def maxDepth(self, root):
if not root:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
else:
return max(left, right) + 1
