原題
給定一個(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