문제48: 균형 이진 트리

재귀 내부의 조건문 하나를 찾지 못했다..

문제

• 높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 말한다

입력

[3,9,20,null,null,15,7]

출력

true

풀이

1. dfs로 깊이를 탐색하며 left와 right의 높이를 비교한다.

def dfs(node):
    if node is None:
        return 0

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

    if left == -1 or right == -1 or abs(left - right) > 1:
        return -1

    return max(left,right) + 1

return dfs(root) != -1

새로운 개념