读前福利
问题描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。
平衡二叉树（Balanced Binary Tree）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
示例：
输入：给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
输出：true
分析问题
平衡二叉树是指二叉树的每个节点的左右子树的高度差的绝对值不超过1。根据定义，一颗二叉树是平衡二叉树，当且仅当它的所有子树也是平衡二叉树，所以，我们可以使用递归的方式来求解，我们根据递归的顺序不同，可以分为自顶向下和自底向上两种方式。
自顶向下方式（先序遍历+判断）
首先我们定义一个函数height，用来计算二叉树中任意一个节点的高度。然后通过先序遍历二叉树，对于当前遍历到的节点，我们首先计算其左子树和右子树的高度，然后判断其左右子树的高度差是否小于1，如果小于1，代表以该节点为根节点的二叉树是平衡二叉树，然后再分别递归地遍历左右节点，并判断左子树和右子树是否平衡。这是一个自顶向下的过程。如果所有子树都平衡，代表该树是一颗平衡二叉树。
我们来看一下代码实现。
class Solution:
def IsBalanced_Solution(self, pRoot):
#求二叉树的高度
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right)) + 1
#如果数为空，代表是平衡二叉树，直接返回
if not pRoot:
return True
#左子树的高度
leftheight=height(pRoot.left)
#右子树的高度
rightheight=height(pRoot.right)
#代表以该节点为根节点的二叉树是平衡的
if abs(leftheight-rightheight) <=1:
#再递归判断其左右子树是否是平衡的
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
return False
自底向上的递归
在上面的算法中，我们可以发现对于同一个节点，函数height会被重复调用，导致执行效率不高，如果采用自底向上的解法，对于每个节点，函数height只会被调用一次。
自底向上的递归是指，我们对二叉树进行后序遍历，对于当前遍历到的节点，我们先递归的去判断其左、右子树是否是平衡的，然后再判断以当前节点为根的二叉树是否是平衡的。如果一棵子树是平衡的，则返回其高度，否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定是不平衡。
下面我们来看一下代码实现。
class Solution:
def IsBalanced_Solution(self, pRoot):
#递归的求树的高度
def height(root):
if not root:
return 0
#左子树的高度
left_height= height(root.left)
#右子树的高度
right_height = height(root.right)
#子树的高度为-1，代表子树不是平衡二叉树，那么该树也不是平衡二叉树，返回-1
#abs(leftHeight - rightHeight) > 1 代表左右子树的高度差大于1，表示该树是不平衡的，返回-1
if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
return -1
else:
#否则，返回树的高度
return max(left_height, right_height) + 1
#如果树的高度不是-1，代表该树是平衡二叉树
return height(pRoot) >= 0
该算法的时间复杂度是O(N)，空间复杂度也是O(N)。
最后
送大家几本比较不错的算法书籍~
小争哥数据结构与算法
链接:https://pan.baidu.com/s/19Jk_G_-QTnGb3GRyzbENgA
密码:keis
谷歌大佬LeetCode刷题指南
链接:https://pan.baidu.com/s/1vtRIsVltTxmIioqqkeSS5g
密码:r3xg
算法小抄
链接:https://pan.baidu.com/s/1rU_T6GRZ-WmV9QFmnJfCBg
密码:unh5
更多有趣内容，请扫码关注一波~
