问题描述

https://leetcode.cn/problems/balanced-binary-tree/description/

解题思路

这题一开始朴素的思路就是，对于每个节点，都计算其是不是平衡二叉树。

计算平衡二叉树的方式是对其求高度。

这会导致我们搜索了2次。

然而我们可以在一次搜索中干这两件事。用-1来标志失衡状态。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        return self.height(root)>=0
    def height(self, root):
        if root is None:
            return 0
        left_height = self.height(root.left)
        right_height = self.height(root.right)
        if left_height == -1 or right_height == -1 or abs(left_height-right_height)>1:
            return -1
        return max(left_height, right_height)+1