[leetcode 2024/02/19] 110. Balanced Binary Tree

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

LeetCode - The World's Leading Online Programming Learning Platform

 

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

이 문제와 유사한 문제라고 할 수 있다. 해당 문제에 로직을 더 자세히 적어놓았다.

 

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