Leetcode 110. 平衡二叉树
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
普通解法
二叉树为高度平衡二叉树，则二叉树中以任意节点为根节点的子树皆为高度平衡二叉树。仿照后序遍历二叉树每个节点，若左子树和右子树皆为高度平衡二叉树，则进一步判断左子树与右子树高度差是否大于一即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
if not self.isBalanced(root.left) or not self.isBalanced(root.right):
return False
return abs(self.depth(root.left)-self.depth(root.right))<2
def depth(self,root:TreeNode):
if not root:
return 0
l=self.depth(root.left)
r=self.depth(root.right)
return max(l,r)+1对于二叉树中高度不同的子二叉树，若其左子树和右子树均为高度平衡二叉树，则需要进一步计算左右子树的高度。即代码流程中存在多次计算子树高度的过程，存在重复的计算，造成性能浪费。
优化解法
观察上面代码中 depth 函数可知，获取二叉树根节点 root 的高度时，需要获取该二叉树中 root 节点以外的所有节点高度，此时自然知晓每个节点的左右子树高度差，即只需要一次计算根节点高度即可完成判断。
对上面代码中 depth 函数稍作改动，在正常的计算左右子树高度外，添加对左右子树高度的差值判断，若差值小于二，则正常执行；否则二叉树为非高度平衡二叉树，直接返回 -1，并在每个递归函数结果处判断返回，避免后续所有的递归取高度值操作。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
return False if self.depth(root)==-1 else True
def depth(self,root:TreeNode):
if not root:
return 0
l=self.depth(root.left)
if l==-1:
return -1
r=self.depth(root.right)
if r==-1:
return -1
if abs(l-r)>1:
return -1
return max(l,r)+1本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.05.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
