110.Balanced_Binary_Tree

My Solution:

python

# 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:
        ans = True
        def height(root):
            if not root:
                return 0
            l_h = height(root.left)
            r_h = height(root.right)
            if abs(l_h-r_h) > 1:
                nonlocal ans
                ans = False
                return 0
            return max(height(root.left), height(root.right)) + 1
        height(root)
        return ans

But exceed time limit.

python

# 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:
        def height(root):
            if not root:
                return 0
            l_h = height(root.left)
            r_h = height(root.right)
            if abs(l_h - r_h) > 1:
                return -1
            # 将 -1 向上传递
            if l_h == -1 or r_h == -1:
                return -1
            return max(l_h, r_h) + 1
        return False if height(root) == -1 else True

为什么原来的解法时间会超时？

因为这个解法将 -1 向上传递了，当一个节点发现其左孙子或右孙子传递的值为-1时，立即返回。而原来的解法中则会继续递归。

时间上更优的解法

python

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_height(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_h = get_height(node.left)
            if left_h == -1:
                return -1  # 提前退出，不再递归
            right_h = get_height(node.right)
            if right_h == -1 or abs(left_h - right_h) > 1:
                return -1
            return max(left_h, right_h) + 1
        return get_height(root) != -1

作者：灵茶山艾府
链接：https://leetcode.cn/problems/balanced-binary-tree/solutions/2015068/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-c3wj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。