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. Constraints: The number of nodes in the tree is in the range [0, 5000].-104 <= Node.val <= 104
# 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 checkdepth(self, root: TreeNode) -> int:
if not root:
return 0
left = self.checkdepth(root.left)
right = self.checkdepth(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return max(left, right) + 1
def isBalanced(self, root: Optional[TreeNode]) -> bool:
return self.checkdepth(root) != -1
Binary Tree인데 균형잡힌(Balanced) 것인지를 판단하는 문제다. 오랜만에 Binary Tree 문제를 풀어보려니 생각이 잘 나지 않아 Discuss 의 다른 사람들 코드를 참고했다.
결론부터 말하면 위의 코드는 Bottom-up 방식의 알고리즘이며, 즉 재귀구조를 사용하여 맨 아래 노드로부터 리턴되는 값(=높이)을 이어받아 최종 높이를 계산하여 균형 여부를 판단하는 것이다.
두 번째 예제를 보도록 하자. 맨 아래 노드까지 계속 내려가다 보면 자식 노드가 없는 노드 [4, 4]의 경우 0을 리턴하게 된다. 그리고 부모 노드인 [3]은 max(0, 0) + 1 의 결과인 1을 리턴한다. 지금부터가 중요한데, [3]의 부모 노드인 [2]는 왼쪽 subtree에 대해선 2를, 오른쪽 subtree에 대해선 1을 리턴한다. 위 코드에서 left, right 각 변수에 재귀구조를 사용했기 때문에 항상 왼쪽, 오른쪽 subtree가 독립적이라고 생각해야 한다.
이렇게 루트 노드인 [1]까지 가면 왼쪽 subtree의 높이는 3, 오른쪽 subtree의 높이는 1이 되어 차이는 2, 최종적으로 -1을 리턴한다. 높이 차이가 2 이상 나면 -1을 리턴하도록 하였기 때문에 최종 결과와 -1을 비교하여 True, False를 구분하는 것이다.
