110 Balanced Binary Tree
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:
- a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
- 이진 트리가 주어졌을 때, 높이 균형(height-balanced)이 맞는 이진 트리인지 여부 확인
- 높이 균형이 맞는 이진 트리?
- 모든 노드의 좌/우 서브 트리 높이가 1 넘게 차이나지 않는 이진 트리
조건
- The number of nodes in the tree is in the range [0, 5000].
- $-104 \le Node.val \le 104$
예제
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))))
- 처음에 왜 모든이 이태릭체로 되어 있었을까 생각하면서 굵게 표시 했었는데, 정작 풀이 때는 간과했다.
- 문제 풀이의 절반은 문제의 이해!!라고 생각해야 문제에 좀 더 집중을 할 거 같다
- 모든 노드의 좌/우 서브트리 높이 차이가 1 이하(no more than 1)인 이진 트리
- 모든 노드? 위의 실패 케이스를 보면, 좌 트리에서는 우측 노드가 계속 빠져 있고, 우 트리에서는 좌측 노드가 계속 빠져있다
- 그래서 안 쪽을 보면 1 초과하여 차이가 아니므로 높이 균형 이진이 아니다
- 어떻게 비교할까?
- 좌/우 트리에서 가장 깊은 곳과 가장 얕은 곳을 찾을까?
- 좌/우 트리 각각 인덱스별로 높이를 저장해두고 비교?
- 애매할 때는 처음부터 무엇을 구해야 하는지 다시 생각해 보자
- 좌/우 트리에서 어떤 단계에서든 높이 차가 1을 넘는 경우에는 false
- 그럼 트리 뎁쓰별로 노드가 존재하는지 먼저 확인을 해보자
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 좌/우 높이 균형이 맞는지
- 높이의 균형이 맞다는 건 어떻게 알 수 있을까?
- 좌/우 서브 트리의 높이 차가 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
- 노드가 존재하면 계속 들어가면서, 깊이를 구한다
- 그 차이가 1 이하면, 더 큰 높이를 반환하고, 2 이상이면 False를 반환한다
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
- 기저 케이스를 0으로 두고, 1씩 높이면서 높이를 측정해 나간다
- 좌/우 높이 차가 1보다 크면 -1을 반환
- 결국 핵심은,
- 좌/우 서브트리의 높이를 계속 빼서 그 차가 1보다 큰지 확인하는
abs(left - right) > 1 - 그리고 만약 차이가 1보다 크지 않다면, 더 큰 높이를 반환하는
max(left, right) + 1
- 좌/우 서브트리의 높이를 계속 빼서 그 차가 1보다 큰지 확인하는