[競プロ]二分木の高さのバランスが取れているかどうかの判定

二分木の高さのバランスが取れているとは

二分木の高さのバランスが取れている（height-balanced）とは、
二分木において、全てのノードの左右の部分木の高度差の絶対値が1以下であること。

問題

Leetcode 110.Balanced Binary Tree

アルゴリズム

ボトムアップとトップダウンのアルゴリズムが考えられる。

ボトムアップ

Python code

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.recur(root) != -1

    def recur(self, root):
        if not root:
            return 0
        left = self.recur(root.left)
        if left == -1:
            return -1
        right = self.recur(root.right)
        if right == -1:
            return -1
        return max(left, right) + 1 if abs(left - right) < 2 else -1

recur(root):

• 再帰の戻り値
  • rootノードの左右の部分木の高度差＜2の場合、rootノードの最大高度(max(left, right) + 1)を返す。
  • rootノードの左右の部分木の高度差＞＝2の場合、高さのバランスが取れていないので-1を返す。
• 再帰の停止条件
  • 葉ノードの先にあるNoneノードは、高さ0を返す。
  • 左or右部分木の高さが-1の場合、左or右部分木は高さのバランスを取れていないので-1を返す。

計算量: O(N) (最悪の場合全てのノードを辿るため)

トップダウン

Python code

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and self.isBalanced(
            root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if not root:
            return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

depth(root):

• 再帰の戻り値：
  • 左右部分木の最大高度+1を返す。
• 再帰の停止条件：
  • 葉ノードの先にあるNoneノードは、高さ0を返す。

計算量:　O(NlogN)

メモ