Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 110. Balanced Binary Tree

tags: leetcode

問題

イデア

二分木が与えられるので,その木が高さがバランス木かどうかを判定しろという問題です.

高さがバランスとは

左右部分木の全てのノードの高さの差が1しかない

ことを言うらしいです.

高さを求めることと,boolを返すことの2つに機能を分割するのが良さそうです.

解法

  • 高さを求める関数内関数get_heightを求めます.
    • 現在のノードが葉ならば0を返します
      • 左と右の深さを求め,どちらかが-1ならば-1を返します.
    • 左右部分木を比較して,高さの違い1以下ならばそのうち大きい方を返します.
      • そうでないならば-1を返します.
      • これで1つでも-1になるならば他の根での実行結果も-1になります.
  • 最後にこの関数を実行して-1でなければ,この二分木の高さがバランスであると言えます.

計算量

ノードの数を$N$,木の深さを$H$とします.

  • 時間計算量
    • 全てのノードを走査するので$O(N)$
  • 空間計算量
    • 木の深さだけ再帰関数を実行するので$O(H)$

Python

# 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:
        if not root:
            return True
        def get_height(cur_node: TreeNode) -> int:
            if not cur_node:
                return 0
            
            left_depth = get_height(cur_node.left)
            if left_depth == -1:
                return -1
            right_depth = get_height(cur_node.right)
            if right_depth == -1:
                return -1
            
            if abs(left_depth - right_depth) <= 1:
                return max(left_depth, right_depth) + 1
            else:
                return -1
        return get_height(root) != -1