LeetCode/Balanced Binary Tree

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 코 m / p 로 b ㎇ ms / 바센 세 d 비나 ry t 네 / ]

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 depth of the two subtrees of every node never differ by more than 1.

Example 1:
Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false.

어떤 subtree 사이의 깊이 차이가 1 이하인 트리를 balanced binary tree라고 합니다.
tree가 balanced binary tree가 되어 있는지 판단하라는 문제입니다.

해답·해설

해법 1

subtree의 깊이의 차이로부터 balanced한 상태인지 판정하는 문제이므로, subtree의 깊이를 취득하면서, 좌우의 subtree의 깊이의 차이가 1 이하인지를 판정하는, 재귀적인 처리를 쓰는 것으로 해 합니다.
이하에서는 check 함수를 정의해, (subtree의 깊이, 좌우의 subtree간의 깊이의 차이가 1 이하인지의 boolean)를 tuple로 돌려주는 구조로 해, root가 없는 말단에서는 (0, True)를 돌려주는 것으로, 재귀적인 처리를 겁니다.
isBalanced 함수의 반환 값은 tuple의 두 번째 요소를 반환합니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

def check(root):
    if not root:
        return (0, True)
    l_depth, l_balanced = check(root.left)
    r_depth, r_balanced = check(root.right)
    return max(l_depth, r_depth) + 1, l_balanced and r_balanced and abs(l_depth - r_depth) <= 1

class Solution:
    def isBalanced(self, root):
        return check(root)[1]

iterative인 코드는 조금 길어지므로, recursive가 좋다고 생각합니다.
생각은 같지만, 다른 쓰는 방법을 하면 예를 들면 이하와 같다.

def check(root):
    if not root: return 0
    l_depth = check(root.left)
    r_depth = check(root.right)
    if l_depth == -1 or r_depth == -1 or abs(l_depth - r_depth) > 1: return -1
    return max(l_depth, r_depth) + 1

class Solution:
    def isBalanced(self, root):
        return check(root) != -1