leetcode - Tree - Balanced Binary Tree

 

이번 문제는 주어진 트리가 높이 균형 트리인지 판단하는 문제입니다.

왼쪽 노드와 오른쪽 노드의 depth 차이가 1이하여야만 합니다.

 

풀이로는 재귀를 통해 각 노드를 순회하면서 depth를 아래부터 1씩 증가시키면서 매깁니다.

depth를 매기면서 각 왼쪽과 오른쪽의 depth를 비교하여 1보다 크면 불균형으로 판단하도록 하였습니다.

 

풀이는 아래와 같습니다.

 

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

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

        res = self.searchDepth(root)
        if res == -1: return False
        return True

    def searchDepth(self, root: TreeNode):
        if root == None: return 0

        right_depth = self.searchDepth(root.right)
        if right_depth == -1 : return -1
        
        left_depth = self.searchDepth(root.left)
        if left_depth == -1: return -1
        
        if abs(right_depth - left_depth) > 1: return -1
        
        return max(right_depth, left_depth) + 1