[Leetcode] 110. Balanced Binary Tree_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '110. Balanced Binary Tree'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Balanced Binary Tree' 알고리즘 문제

 

STEP 2. 'Balanced Binary Tree' 코드(code)

 

STEP 3. 'Balanced Binary Tree' 해설

 

STEP 4. 'Balanced Binary Tree' solution

 

반응형

 

STEP 1. 'Balanced Binary Tree' 알고리즘 문제

 

Given a binary tree, return true if it is height-balanced and false otherwise. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

 

이진트리 구조가 주어졌을 때 높이에 대해 밸런스가 맞으면 True, 아니면 False를 반환하세요. 높이에 대한 밸런스는 왼쪽, 오른쪽 서브트리의 노드의 개수 차이가 1보다 작아야 하는 것을 의미합니다.

 

 

Constraints:

 

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

 

---

STEP 2. 'Balanced Binary Tree' 코드(code)

 

■ Runtime: 4ms Beats 48.63%
■ Memory: 19.04MB Beats 7.24%

 

# Definition for a binary tree node.
# 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:
        self.isBalanced = True

        def dfs(node):
            if not node:
                return 0

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

            if abs(left_depth - right_depth) > 1 : 
                self.isBalanced = False
           
            return 1 + max(left_depth, right_depth)
        
        dfs(root)
        
        return self.isBalanced

---

STEP 3. 'Balanced Binary Tree' 해설

 

전역 변수로 깊이 밸런스를 판단하는 값을 저장하고, 왼쪽 노드와 오른쪽 노드의 길이 차이가 1이 넘을 경우, Fasle를 반환하도록 구성합니다. 이는 빈 노드일 경우 True를 반환하고, 문제가 있을 경우에만 False를 반환하기 위함입니다. 다만 중간에 False 케이스를 발견해도 모든 노드를 순환하게 되기에, 속도 측면에서 비효율성이 있었습니다.

 

 

STEP 4. 'Balanced Binary Tree' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

노드 비교를 통해서 밸런스가 무너질 경우, -1을 리턴하게 됩니다. 해당 노드의 부모 노드도 밸런스를 -1로 계산하여, 불필요한 연산을 진행하지 않게 됩니다.

 

■ Runtime: 3ms Beats 67.88%
■ Memory: 19.28 MB Beats 7.24%

 

# Definition for a binary tree node.
# 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(node):
            if not node:
                return 0
            
            left_depth = dfs(node.left)
            if left_depth == -1 : return -1

            right_depth= dfs(node.right)
            if right_depth == -1 : return -1

            if abs(left_depth - right_depth) > 1 : return -1     

            print(node.val, left_depth, right_depth)
            return 1 + max(left_depth, right_depth)

        return dfs(root) != -1

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '110. Balanced Binary Tree'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.