110. Balanced Binary Tree

주어진 이진 트리가 균형 잡힌 트리인지 확인하세요. 균형 잡힌 트리는 모든 서브트리의 높이 차이가 1 이하인 트리를 의미합니다. 즉, 모든 서브트리가 높이 균형을 유지하고 있는 경우 균형 잡힌 트리입니다.

예를 들어, 다음은 균형 잡힌 트리입니다:

    3
   / \
  9  20
    /  \
   15   7

 

각 서브트리의 높이 차이가 1 이하입니다. 반면에, 다음 트리는 균형 잡힌 트리가 아닙니다:

            1
           / \
          2   2
         / \
        3   3
      / \
     4   4

여기서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 2이므로 균형 잡힌 트리가 아닙니다.

균형 잡힌 트리 여부를 판단하기 위해, 주어진 트리의 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이를 비교하여 높이 차이가 1 이하인지 확인해야 합니다. 이 작업을 트리의 모든 노드에 대해 재귀적으로 수행합니다.

균형 잡힌 트리는 트리의 높이가 더 균등하게 분포되어 있으므로, 높이 차이를 효율적으로 계산하여 모든 노드에서 높이 차이가 1 이하인지 확인하는 것이 중요합니다.

 

public class Solution {
    public bool IsBalanced(TreeNode root) {
        if (root == null) {
            return true; // 빈 트리는 균형 잡힌 트리입니다.
        }
        
        int leftHeight = GetHeight(root.left);
        int rightHeight = GetHeight(root.right);
        
        if (Math.Abs(leftHeight - rightHeight) < 2 && IsBalanced(root.left) && IsBalanced(root.right)) {
            return true;
        }
        
        return false;
    }
    
    private int GetHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = GetHeight(node.left);
        int rightHeight = GetHeight(node.right);
        
        // 높이는 좌우 서브트리 중에서 큰 높이에 1을 더한 값
        return Math.Max(leftHeight, rightHeight) + 1;
    }
}

 

if (Math.Abs(leftHeight - rightHeight) < 2 && IsBalanced(root.left) && IsBalanced(root.right)) {
    return true;
}

IsBalanced 메서드를 호출하는 이유는 현재 노드의 서브트리가 균형 잡힌 트리인지 여부를 확인하기 위함입니다. 이 부분은 트리의 각 노드에서 좌우 서브트리의 균형 여부를 확인하고, 현재 노드의 균형 여부를 결정하기 위한 부분입니다.

특히, 다음 부분에서 IsBalanced(root.left)와 IsBalanced(root.right)를 호출하여 왼쪽 서브트리와 오른쪽 서브트리가 각각 균형 잡힌 트리인지 확인합니다:

 

이 코드는 현재 노드 root의 높이 차이가 1 이하이고, 왼쪽 서브트리와 오른쪽 서브트리 모두가 균형 잡힌 트리일 때 현재 노드 root도 균형 잡힌 트리라고 판단합니다. 이렇게 재귀 호출을 통해 트리의 각 레벨에서 균형 여부를 확인하고, 전체 트리의 균형 여부를 판단하는 방식으로 동작합니다.