110.平衡二叉树

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 这道题是用深搜加上剪枝的算法来做的。
# 遍历每一层节点，从最后一层开始判断，如果两层之差大于2，就直接返回负一
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.recus(root) != -1
    def recus(self,root):
        # 判断根节点是否为None
        if not root : return 0
        left = self.recus(root.left)
        if left == -1 : return -1
        right = self.recus(root.right)
        if right == -1 : return -1
        # 判断左右两个子树的高度差是否小于2，如果是就返回真正的层数（层数多的那个）
        # 如果不是，就返回-1
        return max(left,right) + 1 if abs(left - right) < 2 else -1