1. 문제
leetcode 110. Balanced Binary Tree
이진 트리가 높이 균형인지 판단하라.
높이 균형은 모든 노드의 서브 트리 높이 차이가 1이하인 것을 말한다.
2. 내 풀이
재귀 방식의 dfs를 이용했다. dfs 함수가 자기자신부터 시작하는 트리의 높이를 리턴하도록 했다. 리프노드에 도달하면 1을 리턴하고, 노드가 존재하지 않으면 0을 리턴했다. 리프노드를 제외한 다른 노드에서는 자식 노드의 값 중 큰 값에 1을 더해서 리턴했다. 두 자식 노드에서 리턴한 값 차이가 2 이상이 나면 class 변수 answer을 False로 바꿨다. 탐색이 종료되면 answer를 리턴한다.
3. 전체 코드
'Computer Science > 자료구조' 카테고리의 다른 글
[파이썬 알고리즘] 24. 이진 트리 합의 범위 (0) | 2022.05.06 |
---|---|
[파이썬 알고리즘] 23. 이진 탐색 트리(BST)를 더 큰 수 합계 트리로 (0) | 2022.05.05 |
[파이썬 알고리즘 인터뷰] 22. 배열의 이진 탐색 트리 변환 (0) | 2022.05.03 |
재귀함수를 이용해서 행렬의 곱 구하기 (0) | 2022.01.25 |
[C] 시간복잡도가 O(n)인 재귀함수로 피보나치 수열 구하기 (0) | 2022.01.23 |