[LeetCode 110] Balanced Binary Tree

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

Balanced Binary Tree - LeetCode

Think

재귀로 풀 수 있는 문제

이진트리의 균형은 효율면에서 중요한 부분이라고 한다.

 

 

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def check(root) :
            if not root :
                return 0
        
            #재귀 호출
            left = check(root.left)
            right = check(root.right)
        
            #높이 차이가 나면 -1반환
            #먼저 이미 이 자식노드 들 중 높이차이가 1보다 큰 것이 있었는지 확인
            if left == -1 or \
                right == -1 or \
                abs(left - right) > 1 : #현재 위치에서 높이차이가 1보다 클 때
                return -1
            return max(left, right) + 1
    
        return check(root) != -1 #-1이면 높이차이남. false반환

 

 

 

Get

파이썬에서 \ (백슬래시는 앞뒤 코드가 엔터를 쳤어도 한줄인 것처럼 이어짐을 의미한다!

너무 오랜만에 봣 낯설었다..