leetcode - 균형 이진트리(balanced binary tree)

이진트리야 친해지자..^^

재귀를 쓰더라도 부모 자신부터 처리하고 자식레벨로 넘어가는 상황은 조금이나마 직관적으로 받아들이기가 낫다.

그런데 이 문제처럼 아예 리프 노드부터 처리되고 그 리턴값을 받아와서 그걸로 그 상단 노드가 처리를 해야 할 경우가 아직 어렵다..^^

그래도 요런 아이들도 자꾸 보다보면 익숙해지겠지라는 마음으로 공부공부✍️

1. 손정리

class Solution(object):
    def isBalanced(self, root):
        def DFS(root):
            if not root:
                return 0
            
            left = DFS(root.left)
            right = DFS(root.right)
            
            # 균형이 깨졌음을 알려줄 수 있는 세 가지 지표
            if abs(left-right) > 1 or left == -1 or right == -1:
                return -1
            
            return max(left, right) + 1
        
        return DFS(root) != -1