【LeetCode】 110. Balanced Binary Tree 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

問題

原文

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

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

Constraints:

The number of nodes in the tree is in the range [0, 5000].

-10⁴ <= Node.val <= 10⁴

内容

二分木が与えられます。平衡木であるか調べてください。

※平衡木は左右の子ノードの高さの差が1を超えない二分木です。

※正しくない可能性があります。

方針

・深さ優先探索で再帰的に解く

解答

解答1：

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            #nodeがない場合
            if not node:
                #Trueを返す
                return True
            #左右の子ノードの高さ(平衡でなければFalse)を調べる
            left = dfs(node.left)
            right = dfs(node.right)
            #左右いずれかの子ノードが平行でない、もしくは左右の子ノードの差が1より大きい場合
            if left == False or right == False or abs(left-right) > 1:
                #Falseを返す
                return False
            #平衡な場合は左右のどちらか深い方の子ノードに1を加えて返す
            #1を加えるのは左右の子ノードが親ノードから1階層深いため。
            #maxを取るのは深い方ノードの高さを親に返すため。例2で左側の「2」の深さを調べた時、右側の「3」の深さを返すと平衡木と判断してしまう。
            return max(left, right) + 1
        return dfs(root) != False

class Solution:

def isBalanced(self, root: Optional[TreeNode]) -> bool:

def dfs(node):

#nodeがない場合

if not node:

#Trueを返す

return True

#左右の子ノードの高さ(平衡でなければFalse)を調べる

left = dfs(node.left)

right = dfs(node.right)

#左右いずれかの子ノードが平行でない、もしくは左右の子ノードの差が1より大きい場合

if left == False or right == False or abs(left-right) > 1:

#Falseを返す

return False

#平衡な場合は左右のどちらか深い方の子ノードに1を加えて返す

#1を加えるのは左右の子ノードが親ノードから1階層深いため。

#maxを取るのは深い方ノードの高さを親に返すため。例2で左側の「2」の深さを調べた時、右側の「3」の深さを返すと平衡木と判断してしまう。

return max(left, right) + 1

return dfs(root) != False

補足・参考・感想

参考

前：108. Convert Sorted Array to Binary Search Tree

次：111. Minimum Depth of Binary Tree

LeetCode 解答・解説記事一覧