[LeetCode] 110. Balanced Binary Tree

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (isBalancedHelper(root) == -1) {
            return false;
        }
        
        return true;
    }
    
    public int isBalancedHelper(TreeNode root) {
        if (root == null) { //해당 노드가 null 이라면 0을 반환
            return 0; 
        }
    
        int leftDepth = isBalancedHelper(root.left); //왼쪽 줄기의 깊이를 계산
        int rightDepth = isBalancedHelper(root.right); // 오른쪽 줄기의 깊이를 계산
        
        if (leftDepth == -1 || rightDepth == -1) {
            return -1;
        }
        
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return -1;
        }
        
        return Math.max(leftDepth, rightDepth) + 1; // 왼쪽과 오른쪽 중 더 큰쪽에 1을 더하여 반환
    }
}

 

해당 문제를 풀기 위해서는 우선 Balanced Binary Tree가 무엇인지부터 이해해야 한다.

 

Balanced Binary Tree란 Height-Balanced-Binary-Tree라고도 부르는데 이는 다음과 같은 특성을 가지고 있기 때문에 붙여진 이름이다.

 

1. 어떤 노드에서든, 해당 노드의 왼쪽 서브트리와 오른쪽 서브트리의 깊이 혹은 높이의 차이가 1보다 커선 안된다.

 

예시를 보며 이해하면 편하다.

 

왼쪽의 Binary Tree를 보자.

붉은색 노드 두개를 보면 두 노드 모드 왼쪽 서브트리는 존재 하지 않고 오른쪽 서브트리만 존재하는 것을 볼 수 있다.

오른쪽 서브트리를 보면 2에서 1로 이어지고, 1에서 0으로 이어지는 서브트리를 가지고 있는데, 이 깊이를 계산하면 2라고 볼 수 있다.

 

두 붉은색 노드 모두 왼쪽 서브트리는 가지고 있지 않기 때문에 왼쪽 서브트리의 깊이는 0이라고 볼 수 있다.

 

그러므로 붉은색 노드들의 서브트리 깊이의 차이는 |0-2| = 2 이므로 1보다 크기 때문에 이는 Balanced Binary Tree가 아니다.