剑指 Offer 55-II-平衡二叉树

原题链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

image.png

解题思路：

1. 方法一：递归求出左右子节点的深度，然后对比深度差是否大于1，复杂度较高，会重复计算；
2. 方法二：在递归求左右子节点深度的过程中，加入判断，如果某个节点node的左右叶子节点深度差小于1，则返回该node的深度，否则返回-1，一旦某个节点node的左右叶子节点深度差返回-1，则继续向上返回-1，最终返回False。

# 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:

        def maxDepth(root) -> int:
            if not root: return 0
            return max(maxDepth(root.left), maxDepth(root.right))+1
        
        if not root: return True
        return abs(maxDepth(root.left)-maxDepth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:

        def depth(node):
            if not node: return 0

            left = depth(node.left)
            if left == -1: return -1

            right = depth(node.right)
            if right == -1: return -1

            return max(left,right)+1 if abs(left-right)<=1 else -1

        return depth(root) != -1