리트코드 110번 Balanced Binary Tree (python)

Problem

https://leetcode.com/problems/balanced-binary-tree/description/

Solution

# Definition for a binary tree node.
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    depth = 0

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(node):
            if node is None:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            self.depth = max(self.depth, abs(left-right))

            return max(left, right) + 1

        dfs(root)
        return self.depth < 2

dfs를 통해 탐색하며 왼쪽 자식 노드의 깊이, 오른쪽 노드의 깊이의 차이 최댓값을 구하였다.

Reference

파이썬 알고리즘 인터뷰 48번