Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:     a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

 

思路

　　对于平衡二叉树的判断，我们根据定义来进行判断。任意节点的左右子树的高度差不超过1，关于这点我们可以使用求二叉树的最大深度时的思想，只不过这里有一点区别就是我们需要求每一个节点的左右子树的高度然后比较。如果任意一个节点的左右子树都不满足平衡二叉树的定义的话我们就改变标志量的值，最后判断标志量来返回结果。

解决代码

 

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 # def __init__(self, x):
 4 # self.val = x
 5 # self.left = None
 6 # self.right = None
 7 
 8 class Solution(object):  9     def isBalanced(self, root): 10         """
11  :type root: TreeNode 12  :rtype: bool 13         """
14         if not root: # 节点为空直接返回。 15             return True 16         self.flag = False # 设置标志量 17  self.GetHeight(root) # 对每一个节点的左右子树高度进行判断。 18         
19         return not self.flag 20            
22     def GetHeight(self, root): 23         if not root: # 节点为空直接返回0 24             return 0 25         left = self.GetHeight(root.left) # 当前节点左子树的高度 26         right = self.GetHeight(root.right) # 当前节点右子树的高度 27         if abs(left - right) > 1: # 计算左右子树的高度差 28             self.flag = True # 不满足时，设置标志量 29         return max(left, right)+1                  #  最高的节点数

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄