리트코드) 110. 균형 이진 트리(자바)

균형 이진 트리

https://leetcode.com/problems/balanced-binary-tree

문제 : 이진 트리가 높이 균형인지 판단하라.
높이 균형은 모든 노드의 서브트리 간의 높이 차이가 1 이하인 것을 말한다.

입출력1

입력 : root = [3,9,20,null,null,15,7]
출력: true

입출력2

입력 : root = [1,2,2,3,3,null,null,4,4]
출력: false

풀이

1. dfs를 통해 맨끝까지 간다. 맨끝값은 0을 반환하게 될 것

2. 높이 균형인지 확인한다.
   왼쪽 오른쪽을 비교하여 차이가 2이상이라면 -1
   한쪽이라도 -1이 있다면 결과는 -1

3. 아직 균형이라면 depth를 올린다.
   왼/오 중 더 큰값 + 1 해준다.
   +1을 통해 depth가 달라짐을 표현한 것이라고 봄

// 균형 이진트리 : 왼/오 차가 1이상인지 확인하기
class Solution {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) != -1;
    }

    public int dfs(TreeNode root) {
        if (root == null) { // 맨끝값은 0을 반환하게 될 것
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        // 높이 균형이 아닌 경우
        if(left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        // 왼/오 중 더 큰값 + 1
        return Math.max(left, right) + 1;
    }
}

참고문헌 : 102가지 알고리즘 문제 풀이로 완성하는 코딩테스트 자바 알고리즘 인터뷰 536p