[LeetCode][Grind 75] 110. Balanced Binary Tree

문제 해결 방안

height-balanced하다는 것은, 좌우 노드의 높이 차가 1을 넘지 않는 것을 의미합니다.

그러면 이것을 판단하기 위해서는 각각의 하위 노드들도 전부 height-balanced해야합니다.

'하위의 모든 노드들도 00해야한다'는 의미는 재귀를 통해서 푸는 방법을 사용해야한다고 생각했습니다.

 

재귀에 사용되는 함수 `checkHeight`를 만들어서 사용했습니다.

`checkHeight` 로직

1. 노드가 null이면 높이를 0으로 반환하여 재귀 호출을 종료합니다.
2. 왼쪽 하위 트리의 높이를 계산한 후, `-1`이 반환되면 이미 불균형이므로 그대로 `-1`을 반환하여 더 이상 탐색하지 않도록 합니다.
3. 오른쪽 하위 트리에 대해서도 동일한 과정을 반복합니다.
4. 왼쪽과 오른쪽 높이 차이가 1보다 크면 현재 노드는 불균형 상태이므로 `-1`을 반환합니다.
5. 그렇지 않으면 현재 노드의 높이를 계산하여 반환합니다.

그리고 해당 재귀가 끝나면 `isBalanced` 함수에서 True/False만 판단해서 정답을 제출하게 했습니다.

`isBalanced` 함수는 `-1`이 아닌 경우에 트리가 균형입니다.

 

겪은 문제점

우선 아래에서 부터 재귀를 시작하는건 시작점이 여러개가 되기 때문에 어렵다고 생각했고, 위에서부터 순서대로 재귀를 통해 탐색해 들어가야했습니다.

 

그치만, 어떤 식으로 재귀를 사용해야할지 제대로 판단이 서지 않았습니다.

정답 코드

class Solution {
    public boolean isBalanced(TreeNode root) {
        // checkHeight의 리턴값이 -1이 아니면 true(균형), -1이면 false(불균형)
        return checkHeight(root) != -1;
    }

        public int checkHeight(TreeNode node){
        if(node == null){
            return 0;	// null인 노드는 높이도 0
        }

        // 왼쪽 트리가 불균형 상태면(리턴값 -1) -1 리턴
        int leftHeight = checkHeight(node.left);
        if(leftHeight == -1){
            return -1;
        }

        // 오른쪽 트리도 마찬가지
        int rightHeight = checkHeight(node.right);
        if(rightHeight == -1){
            return -1;
        }

        // 왼쪽 트리와 오른쪽 트리의 높이가 1이상 차이나면 불균형이므로 -1 리턴
        if(Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }

        // 불균형이 아니면 왼쪽 트리와 오른쪽 트리의 높이중 큰것에 +1하여 현재 노드의 높이 리턴
        return Math.max(leftHeight, rightHeight)+1;
    }
}