LeetCode 110(Balanced Binary Tree, Python)

1. 문제 링크

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

2. 문제 설명

• 이진트리가 주어질 때, 이 트리가 height-balanced 되있는지에 따른 boolean을 반환
  • height-balanced의 정의
    • 모든 노드의 두개의 subtree의 depth가 1개보다 더 차이나지 않는 이진트리
  • 예시1) 아래 트리의 경우
    • 루트 노드 3에 대해 subtree의 depth가 왼쪽 오른쪽 각각 1, 2이고
    • 노드 9는 0,0, 노드 20은 각각 1,1로 depth가 1보다 더 차이나는 게 없으므로 True를 반환 
      •     3
           / \
          9  20
              /  \
           15   7
  • 예시2) 아래 트리의 경우
    • 루트노드 1에 대해 subtree의 depth가 왼쪽 3, 오른쪽 1이기 때문에 1보다 더 차이나므로 False를 반환 
      •         1
               / \
              2   2
             / \
            3   3
           / \
          4   4

3. 처음 풀이

• 재귀 규칙을 파악해보기
  • 우선 root가 None이면 양쪽 depth가 둘다 0이기 때문에 1 (True)를 반환
  • 그렇지 않다면, root의 왼쪽 노드가 balanced한지, 오른쪽 노드가 balanced 한지를 파악
    • 왼쪽 노드가 balanced 하지 않거나, 오른쪽 노드가 balanced하지 않거나,
    • 또는 두 노드의 depth 차이가 1보다 크면 False를 반환 
  • 그렇지 않으면, 현재 노드를 포함한 트리의 높이는, 더 높은 subtree의 높이에 1을 더한 값이므로 해당 값을 반환

# 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: 
        
        if root is None:
            return 1

        left = self.isBalanced(root.left)
        right = self.isBalanced(root.right)

        if left is False or right is False or abs(left-right) > 1:
            return False 

        return max(left,right) + 1

4. 다른 풀이

• 다른 사람의 풀이
  
  • 루트 노드가 None이면 True반환
  • 루트의 왼쪽 노드가 balanced 한지 파악하고, 만약 balanced하지 않으면 False 반환
  • 오른쪽 노드가 balanced한지 파악하고, balanced하지 않으면 False 반환하며
  • 위 세가지 케이스에 포함이 되지 않으면 왼쪽 오른쪽 depth의 차이와 1+max(l,r)의 boolean 반환

# 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:
        if not root: 
            return True
        l = self.isBalanced(root.left)
        if not l: 
            return 0
        r = self.isBalanced(root.right)
        if not r: 
            return 0
        return abs(l-r)<=1 and 1+max(l,r)

5. 배운 점

• 최대한 전체 트리로 보려하지 말고, root, root.left, root.right만 살펴보면서 재귀 규칙을 찾기!
• 종료조건 (return)을 파악하고, 그 외의 케이스에는 재귀에 어떤 값을 넘겨야 하는지를 살피기.