# 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