[1스4코2파] # 202 LeetCode 110. Balanced Binary Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (202차)
[4코1파] 2023.01.13~ (194일차)
[1스4코1파] 2023.04.12~ (105일차)
[1스4코2파] 2023.05.03 ~ (83일차)

Today :

2023.07.24 [202일차]
Tree
110. Balanced Binary Tree

110. Balanced Binary Tree

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

문제 설명

binary-tree가 주어졌을 때, height-balanced tree인지 확인하는 것
hight-balnace tree는 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1 이하인 binary tree이다.
hight-balnace binaory tree 예시는 AVL tree, red-black tree 등이 있음!

문제 풀이 방법

dfs 로 탐색하면서 현재 root 노드의 왼쪽 자식과 오른쪽 자식의 height를 구하고 둘의 차를 구하여 절댓값이 1보다 클 경우 false를 return, 아닐 경우 현재 root 노드의 왼쪽 자식과 오른쪽 자식으로 내려가면서 확인한다.

내 코드

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        def dfs(root):
            if not root: return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            balance = (left[0] and right[0] and 
            abs(left[1] -right[1]) <=1)

            return [balance, 1+max(left[1], right[1])]

        return dfs(root)[0] 

증빙

여담

Tree 어려웡