[파이썬 알고리즘] 21. 균형 이진 트리

1. 문제
leetcode 110. Balanced Binary Tree
이진 트리가 높이 균형인지 판단하라.
높이 균형은 모든 노드의 서브 트리 높이 차이가 1이하인 것을 말한다.

2. 내 풀이
재귀 방식의 dfs를 이용했다. dfs 함수가 자기자신부터 시작하는 트리의 높이를 리턴하도록 했다. 리프노드에 도달하면 1을 리턴하고, 노드가 존재하지 않으면 0을 리턴했다. 리프노드를 제외한 다른 노드에서는 자식 노드의 값 중 큰 값에 1을 더해서 리턴했다. 두 자식 노드에서 리턴한 값 차이가 2 이상이 나면 class 변수 answer을 False로 바꿨다. 탐색이 종료되면 answer를 리턴한다.

3. 전체 코드