미소를뿌리는감자의 코딩
[leetcode 2024/02/19] 110. Balanced Binary Tree 본문
https://leetcode.com/problems/balanced-binary-tree/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. 접근 방법
balanced가 되었는지 확인하기 위해서는, 해당 노드에서 abs(왼쪽 노드의 최대 깊이 - 오른쪽 노드의 최대 깊이) < 2 이어야 한다.
재귀적으로 밑에 노드들도 다 확인하기 때문에 abs(왼쪽 노드 최대 깊이 - 오른쪽 노드 최대 깊이) < 2 를 해도 괜찮다.
self.balanced라는 변수를 이용해서, max( self.balance, abs(left_depth - right_depth))를 통해, 최대 차를 저장해둘 것이다.
따라서 현재 노드에서는 abs(left_depth - right_depth)를 계산해주고,
return 1 + max(left_depth, right_depth)를 통해 부모 노드에 긴 depth를 전달해 줄 것이다.
https://potatoscatteringsmile.tistory.com/127
[leetcode 2024/02/19] 543. Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/description/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for
potatoscatteringsmile.tistory.com
이 문제와 유사한 문제라고 할 수 있다. 해당 문제에 로직을 더 자세히 적어놓았다.
2. 코드
# 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
import math
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
self.balanced = 0
def depth(node):
if not node:
return 0
left_depth = depth(node.left)
right_depth = depth(node.right)
self.balanced = max(self.balanced, abs(left_depth - right_depth))
return 1 + max(left_depth, right_depth)
depth(root)
if self.balanced > 1:
return False
return True
-- 더 복잡하게 짠 코드 --
# 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:
t_height = []
total_height = []
def h_node(node, height, t_height):
if node is None:
t_height.append(height)
return
h_node(node.left, height + 1, t_height)
h_node(node.right, height + 1, t_height)
def every_node(node):
if node is None:
return
t_height_left = []
h_node(node.left, 0, t_height_left)
left = max(t_height_left) if t_height_left else 0
t_height_right = []
h_node(node.right, 0, t_height_right)
right = max(t_height_right) if t_height_right else 0
total_height.append(abs(left-right))
every_node(node.left)
every_node(node.right)
every_node(root)
print(total_height)
return max(total_height) <= 1 if total_height else True
'코딩 테스트 > leetcode' 카테고리의 다른 글
[leetcode 2024/02/22] 75. Sort Colors (0) | 2024.02.22 |
---|---|
[leetcode 2024/02/22] 179. Largest Number (0) | 2024.02.22 |
[leetcode 2024/02/19] 543. Diameter of Binary Tree (0) | 2024.02.19 |
[leetcode 2024/02/17] 938. Range Sum of BST (1) | 2024.02.17 |
[leetcode 2024/02/17] 700. Search in a Binary Search Tree (0) | 2024.02.17 |