leetcode 110. Balanced Binary Tree(python)

語言: CN / TW / HK

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

描述

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Note:

The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104

解析

根據題意,給出了一個二叉樹,檢查這個二叉樹是不是高度平衡的。

高度平衡的二叉樹,就是指每個節點的左子樹和右子樹的高度相差不超過 1。

這道題其實和 leetcode 108. Convert Sorted Array to Binary Search Tree 考察的內容一樣,都是計算樹的深度,那道題都會做這道題也是類似的。

定義一個函式 depth 用來計算某個節點的高度,如果節點為空就直接返回 0 。如果不為空則繼續深入它的左右兩個子樹計算當前節點的高度。

定義一個函式 isBalanced 用來判斷當前節點是否是平衡的二叉樹,通過 depth 可以得到其左右子樹的高度 l 和 r ,然後比較當前節點是否左右子樹的高度差小於 2 且左右兩個子樹也是高度平衡二叉樹。

解答

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:return True
        def depth(root):
            if not root:return 0
            return max(depth(root.left), depth(root.right)) + 1
        l = depth(root.left)
        r = depth(root.right)
        return abs(l-r)<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

執行結果

Runtime: 56 ms, faster than 48.18% of Python online submissions for Balanced Binary Tree.
Memory Usage: 17.6 MB, less than 88.07% of Python online submissions for Balanced Binary Tree.

類似題目

原題連結:https://leetcode.com/problems/balanced-binary-tree/

您的支援是我最大的動力 !!!