110 Balanced Binary Tree

문제

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:

조건

예제

      3
  9        20
       15        7
Input: root = [3,9,20,null,null,15,7]
Output: true

              1
        2          2
    3       3
 4     4

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Input: root = []
Output: true

해결

1st

1 생각

1 코드

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: TreeNode) -> bool:
        if not root:
            return True
        # AttributeError: 'NoneType' object has no attribute 'val'
        if not root.val:
            return True

        def dfs(node: TreeNode, depth):
            if not node:
                return depth - 1

            return max(dfs(node.left, depth + 1), dfs(node.right, depth + 1))

        return abs(dfs(root.left, 1) - dfs(root.right, 1)) <= 1

1 결과: 실패

202 / 228 test cases passed. Status: Wrong Answer

Input: [1,2,2,3,null,null,3,4,null,null,4]
Output: true
Expected: false

2nd

2 생각

# [1,2,2,3,null,null,3,4,null,null,4]
'''
          1 ------------- 1
       2     2 ---------- 2
    3           3 ------- 3
 4                 4 ---- 4
'''
case3 = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4), None)), TreeNode(2, None, TreeNode(3, None, TreeNode(4))))
2 좌/우 서브트리 뎁쓰별로 노드가 존재하는지
def bfs(node: TreeNode):
    res = []
    if not node:
        return res

    queue = [node]
    res.append(node.val)
    while queue:
        node_curr = queue.pop(0)

        if not node_curr.left and not node_curr.right:
            continue

        if node_curr.left:
            res.append(node_curr.left.val)
            queue.append(node_curr.left)
        else:
            res.append(None)

        if node_curr.right:
            res.append(node_curr.right.val)
            queue.append(node_curr.right)
        else:
            res.append(None)
            
    return res
  
  list_left = bfs(root.left)
  list_right = bfs(root.right)
  print(list_left)
  print(list_right)

# [1,2,2,3,3,null,null,4,4]
list_left = [2, 3, 3, 4, 4]
list_right = [2]

# [3,9,20,null,null,15,7]
list_left = [9]
list_right = [20, 15, 7]

# [1,2,null,3]
list_left = [2, 3, None]
list_right = []

# [1,2,2,3,null,null,3,4,null,null,4]
[2, 3, None, 4, None]
[2, None, 3, None, 4]
2 좌/우 높이 균형이 맞는지
# False
# [1,2,2,3,3,3,3,4,4,null,null,4,4,null,null,5,5]
            1 --------------------- 1
      2            2 -------------- 2
   3     3      3     3 ----------- 3
 4   4        4   4 --------------- 4
5 5 ------------------------------- 5

# False
# [1,2,2,3,null,3,null,4,null]
          1 -------------------- 1
      2       2 ---------------- 2
   3        3 ------------------ 3
4 ------------------------------ 4

# False
# [1,2,2,3,null,null,3,4,null,null,4]
          1 ------------- 1
       2     2 ---------- 2
    3           3 ------- 3
 4                 4 ---- 4

2 코드

def isBalanced(self, root: TreeNode) -> bool:
    if not root:
        return True

    def dfs(node: TreeNode, depth):
        if not node.right and not node.left:
            return depth
        
        # 좌 또는 우 노드 하나만 있어도 위의 if문을 통과하므로,
        # 깊이가 깊어져도, depth가 계속 유지되는 것 같지만,
        # return하다보면 dfs를 들어가지 못해서 좌 또는 우 어떤 노드에 과거 값이 남아 있어서 차이가 발생하면 False 반환
        dfs_left = depth
        dfs_right = depth
        if node.left:
            dfs_left = dfs(node.left, depth + 1)
        if node.right:
            dfs_right = dfs(node.right, depth + 1)

        # print('dfs_left: ', dfs_left, ', dfs_right', dfs_right)
        if dfs_left is False or dfs_right is False:
            return False
        
        if abs(dfs_left - dfs_right) <= 1:
            return max(dfs_left, dfs_right) # 이렇게 int 또는 bool 타입으로 반환하는 것은 별로 안 좋은 거 같다. 다음부터는 리턴 타입의 일관성도 고려 필요.
        else:
            return False

    if dfs(root, 1) is False:
        return False
    else:
        return True

2 결과: 성공

Runtime: 44 ms, faster than 92.48% of Python3 online submissions for Balanced Binary Tree.
Memory Usage: 19.6 MB, less than 5.12% of Python3 online submissions for Balanced Binary Tree.

3rd 책

책 풀이

def solution_by_book(self, root: TreeNode) -> 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:
            return -1

        return max(left, right) + 1
    
    return check(root) != -1